I don't mean to hijack this thread - but I was having the same exact problem (I think).
My paypal isn't working either - and when I use the sand box dev testing with this - and then I add your code to make it print out the explanation - I get the same error message:
<ErrorCode>111210</ErrorCode><ErrorDescription>The requested service is unavailable between the selected locations.</ErrorDescription></Error></Response></RatingServiceSelectionResponse>
And my sender address is fine - has the correct address and country code - however there is NO ship TO address.
When someone clicks on a product - and the adds it to the cart, and then they choose to pay via PayPal - PowerStore does NOT require them to be logged in or add any profile information or ship to information - so how could it possibly have the ship to information if it doesn't even ask for it yet? I assume that's the problem right? All the ship to fields are blank at this point...