There are 2 parameters that are being passed to paypal that impact this behavior.
address_override:
It is hard coded to address_override=1 in the PayPal Standard Payment Processor. This overrides the address that paypal has with the address being passed in. Certain required fields, such as State have to match, if not then the validation error occurs. If changed to address_override=0 then the address used is the address stored in paypal.
no_shipping:
Prompt buyer for shipping address. Allowed values are:
0: (default) buyer is prompted to include a shipping address.
1: buyer is not asked for a shipping address
2: buyer must provide a shipping address
In the plugin if the order does not require shipping then its set to no_shipping=1 otherwise, it is set to no_shipping=2.
I would contend to change it for all orders to:
address_override=0
no_shipping=1
This would eliminate the need for address validation, and since nopCommerce collects and stores the shipping address I really do not see the need to pass it to paypal for payment processing.