You can still get free Quest bars from their website. I like the taste better than those Atkins protein bars, which I used to eat. Less glycemic, also.
But as far as whether protein bars are Paleo, no. It's a manufactured snack designed to simulate you eating Milky Ways without the sugar.
You can get the simplest Whey powder out there, make a shake, and augment with what you want instead of having something already done. You'll kind of get your perfect product that way. Or make your own, here is one from Marks Daily Apple that looks really tasty and contains whey. I've heard that Lara bars are good, look at the labels as some have more sugar content than others, and those Raw Crunch bars I've had a few times, the chocolate one is yum.
Or.. cook and cut steak in bar shapes and tote that along :)
It is likely better to drink Whey Powder.
If you do go with a bar you would want to avoid soy and look for something with Whey.
Epic Bars are amazing--kind of like a jerky/pemmican bar; our local health food store sells them but you may also find them online... Not sure if all flavors are 100% paleo but they are the closest thing I have found so far...
Here is a great breakdown of 6 Protein Bars on the PaleoHacks blog that Casey Thaler just put together.
The Advanced Athletics protein bars are paleo friendly. They use grass fed whey protein, have only 2g of sugar, no gluten, no soy, and no grains of any kind.
To rephrase, "Asking on a paleo site about a Protein Bar is like buying a chair about jogging"
Though whey may seem like a good idea, I think it's would be silly to use it in a paleo diet : the simple fact that it gives me bad acne means there's something wrong with it.
I'd use Beef Gelatin. Grass-fed if possible.
I like Lara Bars. A few of them are paleo friendly and tasty too. For protein shake I use Omega Nutrition Certified Organic Pumpkin Seed Protein Powder mixed with coconut milk and frozen berries. It's very good.
I've heard some great reviews on Steve's Original Paleo Kits and Mark Sisson's Primal Snack Packs. It also depends on the purpose of the protein bar. Are you looking for a healthy snack, a meal replacement, or pre/post workout nutrition?
Beef Jerky is paleo. And shaped like a bar. Sorta.