Can you add an extra input field to your form and see if it changes anything?
<input type="hidden" name="charset" value="utf-8">
Check this as well: http://www.nopcommerce.com/boards/t/19293/paypal-greek-characters.aspx#84782 I don't have access to a PP Sandbox at the moment, otherwise I'd attempt to help more.