Just testing a new site that is on a local server and am getting the above-noted message.
I see that another thread was created over the same problem, but it appears to have been dropped.
Here's the link (tried the link button above, opening it at the start of a line of text, entering the URL, then closing it after the text, but couldn't get it to work for me): https://premium.wpmudev.org/forums/topic/paypal-does-not-allow-your-country-of-residence-to-ship-to-the-country-you-wish-to#post-116303
I've tried different ship-to addresses, different ship-from addresses (made sure that both are different), have enabled shipping to all countries, but nothing seems to work.
I should add that I'm on the latest version of MarketPress (2.5.4).