After finally deciding to just delete and reinstall the plugin (v3.5 again) my problem was solved.
Is there maybe any possibility the profile based-setting did not update correctly when updating the Shopping Cart settings?
In the beginning I had profile based shipping checked but decided not to use this setting after all. When I got around to testing the checkout process shipping costs as said did not get displayed in PayPal, whether profile based was checked or unchecked.
mra13, after I reinstalled and the checkout did handle shipping costs as should I just checked and unchecked profile based again to see if the issue would reappear and it indeed had been the root of the problem. Can’t say if it was now, the problem for me has not reoccured since.