Zen Cart can run okay on most shared-hosting-accounts.
Your shared-hosting may have peculiar SSL requirements, so you may not be able to offer SSL if the server uses proxying to provide SSL capability.
I've no idea what you mean by "with cache enabled".
I can't tell you whether you need to upgrade or not. Your hosting company probably knows better. It would be smart to get the "technical why or why not" behind their claims.
As far as PayPal goes, Zen Cart supports PayPal Express Checkout already. You simply need to do a couple configuration steps to tell it which PayPal account to deposit into.
.
Zen Cart - putting the dream of business ownership within reach of anyone!
Donate to: DrByte directly or to the Zen Cart team as a whole
Remember: Any code suggestions you see here are merely suggestions. You assume full responsibility for your use of any such suggestions, including any impact ANY alterations you make to your site may have on your PCI compliance.
Furthermore, any advice you see here about PCI matters is merely an opinion, and should not be relied upon as "official". Official PCI information should be obtained from the PCI Security Council directly or from one of their authorized Assessors.