What I experienced was similar to what is posted in this thread.
The account only had a name & email associated with it, and we were making a first purchase with Paypal.
The checkout page did not give an option to type in the address, so we went and added billing & shipping, but Paypal checkout won’t pick it up.
We got an error identical to @khan’s in post #8 above.
It worked out when we logged in with a different browser.