wpegg: Change your bank (and tell them that's why). Not every one does, and Paypal payments are just straight conversion.
Kabuto: They certainly are not. Paypal does charge 2.5% for transactions involving a currency conversion. Most major banks do the exact same thing for straight credit card purchases. Some banks are just extra annoying and charge additional fees.
As long as they keep this 2,5% - that's a fair fee. They get also some profit on exchange rate. But minimum charge (like 2,5% not less than $3) - that's just theft.
EinhanderZwei: Thanks for fast and clear replies!!!
See if banks in Ukraine sell pre paid debit cards. Very convenient payment method - just buy it 'from shelf' and that's it. No name on it, don't have to have an account in this bank etc. I use it such card and it never failed me.. Of course – before check if the fee you mentioned doesn’t apply to pre paid cards sold in Ukraine as well :-)