Implementation depends on the payment provider you use. It can also be done with either individual ecart rules, or managed through a database table.
You do need to make sure that you update the shipping based on the paypal shipping state selected if it changes. That would be automatic if you use individual ecart rules, and can be easily accounted for by doing another lookup in the database table if you use that route.
If you .zip a copy of your checkout pages (checkout, confirm, pp_confirm, confirm_cart) then I can take a look and be more specific.