The first thing you're going to need to decide is what shopping cart/platform to choose. WordPress is a blogging platform (or at best, a very simple CMS). It is not
an eCommerce platform.
Since you said you'd be using PayPal, you have plenty of options to choose from. Magento
are two popular (and free) options, but they're certainly not the only ones. Since they both offer a demo of some kind, play around with each and see what you like. Magento is geared more toward larger sites/businesses and requires more resources, but is more customizable "out-of-the-box" than osCommerce. osCommerce is for smaller sites and is less customizable (without custom programming), but its hosting requirements are much lower.
With domains, you can really get one from just about anywhere, but read everything
you sign; some less scrupulous companies will try to tack on additional products and services without providing an easy way to say "no" (1&1 and GoDaddy have been the worst offenders in my limited experience). It's also a bad idea to host with the same company providing your domain name (for a variety of reasons: control, security, and business continuity come immediately to mind).
As for hosting, without knowing what kind of traffic you expect and shopping cart you choose, it's hard to make an informed recommendation.