rflush, if PHP session doesn’t work on your server then pretty much none of the wordpress shopping cart plugin will work on your site as they all uses the PHP session variable.
with that said, I am sure your hosting provider will address the issue if you explain to them properly. (I can’t think of any hosting provider that would sell you hosting with PHP where PHP session doesn’t work! They would have to be a really crappy hosting provider to do that).
Just ask them if they can make sure that the PHP Session is working (this has got nothing to do with PayPal or anything else).