I think the most effective strategy for the average person is to shop for their lean meats and veggies on a day that you have off work and prepare a large number of meals upfront and freeze some. To meet the minimum requirement for Paleo you can buy good ingredients at your local supermarket. If you want to go a little more down the proverbial rabbit hole you can buy grass-fed beef and bison as well as free-range chicken and wild caught fish. Check the web for local farmers' markets as well. It is unlikely that we will ever find convenient pre-made meals in our supermarkets that are Paleo as the higher degree of processing required would take such meals out of line with the dietary philosophy. For small snacks you can combine dried fruits (no added sugar), unsalted nuts, and jerky.
All that being said their are services out there that you can find. It might take some searching on Google or networking. My wife, for example, prepares Paleo meals for a few people I work with. We do lunch-hour crossfit sessions and many of the participants are Paleo eaters. So you might find someone like that who could shop and prepare the meals for you. She charges $5.00 per meal (but it's just for the people I work with, sorry!).
Here are some links for you that might help:
http://www.paleobrands.com/
http://www.paleoplan.com/resources/sampler-menu-meal-plan/
http://robbwolf.com/2011/01/16/pre-cooking-paleo-diet-food/