The good news is you can start with any plan you want and upgrade later.
You don't really need the IP or cert for PayPal, so from here on, read as though you plan on expanding later.
The high end plan comes with an IP, which you can add to any plan for $3.95/month. It also come with an SSL cert--but you can also buy those anywhere and add them to any plan, once you add a dedicated IP.
Do you need VPN? That's probably the main thing you get with the high end plan, that doesn't come with the others.
Besides that, it's pretty much a matter of disk space and bandwidth, which even the cheapest plan comes with plenty of. I'd just go down the comparison page and figure out what's best for you.
Code Monster also has the advantage of the sale price, which might not last forever -- but you are locked in at that pricing if you buy during the sale. You could lock into that pricing, then downgrade later if it's more than you need, or upgrade if you need more.
If you think you can get by with that, I'd probably get CodeMonster, add an IP (when the time comes), get a cert (Godaddy is pretty cheap for those, plus I believe they throw in a free domain when you buy one from them) -- then install the cart of your choice.
DH has Zen Cart in the one-click installs, but you can pretty much install what you want. Zen is a popular spin-off of OSCommerce, which is also a popular choice.
Save up to $96 at Dreamhost with ALMOST97 promo code (I get $1).
Or save $97 with THEFULL97.