Hebrew in Paypal turns into characters and symbols gibberish

We have a form in Hebrew. When the form is submitted to PayPal, the description turns to Gibberish - symbols and characters. See screenshot: http://screencast.com/t/82YAaD11fY

When I wrote to PayPal about this, they said:
Assuming Gravitiy Forms allow access to API parameters, you would probably like to set the Israeli locale so that all checkout pages will appear in Hebrew.

You can do this by adding the following parameter to your SetExpressCheckout request: LOCALECODE=he_IL

Hebrew is definitely supported, it is probably a URL-encoding issue.
Please try removing your URL-encoding (if you are encoding). If that doesn’t help, then you need to check the specific URL-encode method you use and set the correct default charset.

Help!
Rebecca