A Yahoo! Store is where we first started. We migrated when we found that we had outgrown them.
However, that was before they offered so many features. If they'd had everything they do today back then, who knows if we would have switched?
A Yahoo! Store is much more than a shopping cart, and it's so cheap for what you get. I don't know too much about Paypal's shopping cart product, but it sounds like it's just a shopping cart...
In short, I highly recommend a Yahoo! Store.