@Ttae
Is the home address which you have registered with PayPal in the UK?
It's a couple of years since I last paid by PayPal, but my recollection is that I had to authorise PayPal to give Vodafone my home address. In my experience, it's relatively unusual for that information to be required, but I assume that Vodafone requires assurance that they are being paid from a UK PayPal account.
I understand why they only accept UK-registered credit and debit cards, as there is a fraud risk with such transactions, but I'm not sure why they should extend it to PayPal.
It may be that there is some other explanation, but I can only suggest doing your top-up at a Vodafone store, or buying a top-up voucher at a supermarket or convenience store.
