Hi markustm, I have a paypal account but it is linked to my overseas account for which i have online banking. Istri has one as well but her's is linked to her credit card. If you have an overseas account or credit card, link the paypal account to it and you shouldn't have any problems.
Having said that, I did open my paypal account with my australian address and after verification then changed it to my Indonesian address. Hope this is of some help to you.