The short answer: yes
The long answer: they could cause many issues for someone needing to improve digestion, regulate blood sugar, reverse insulin resistance and lose weight.
Proceed with caution. Timing of them is critical.
As you can see by the previous answers, it's a big grey area. This is one you have to try and see for yourself.
I started out avoiding them because Cordain, et. al. said they were bad. Then I read some more reasonable stuff from Lalonde (I'm biased because we're both chemists, so I trust him more) which pointed out that the bad stuff in potatoes doesn't survive cooking or digestion. So now, I do a baked potato a day after my workout to replenish my glycogen, it's a great source of tasty starch without any fructose. I cook the hell out of them so there isn't much, if any, bad stuff left in them.
However, if you react to nightshades like this person, then stay away from them: http://robbwolf.com/2012/04/09/putting-hidradenitis-suppurativa-remission-paleo/
The only right answer here is: "how does it make you look, feel, and perform?" Don't fall into any paleo dogma where food are or aren't paleo. Use paleo as a framework to form hypotheses to guide your choices, not dictate them.
Actually, the short answer: No.
A potato is a product of agriculture - it's a nightshade, it would have come into existence around the neolithic. So strictly speaking, paleolithic men & women would not have consumed it.
Having said that, in a broader scope, it's as much a paleo food as a tomato.
If we're simply talking nutrient for nutrient - it's a whole food. It can play a part in a paleolithic way of eating if, as mentioned, timed efficiently. Sweet potatoes are a preferred source of starchy carbohydrates for those opting to consume starchy tubers - I'd recommend the same for the added vitamins & lower GI response.
Cordain still says no. Guyenet says yes, as long as you peel it. I can get away with the occasional potato, but constant exposure causes serious problems. A few folks suggest the best way to delineate what foods are in is 'can you eat it raw'? Interestingly enough, potato is not very edible raw, but sweet potato is. I don't know how accurate this rule of thumb is- one can at least assume cooking will destroy many of the more troublesome plant chemicals.
If you have problems with blood sugar/insulin just say no.
I also never count calories and my body fitness has improved greatly along with my strength and performance. I eat about 85% paleo with a splurge here and there. Every kind of food is not good... many types of food are actually very bad and you can feel just how much they hurt you after you have been eating clean for a while.
Can you eat it raw? That's my first rule of thumb in determining if something is paleo.
If you look at any list of non-paleo foods you'll see its dominated by foods that are indigestible in their raw form (gains, legumes, etc...) The theory goes that we never adapted to these foods, because we couldn't eat them in their raw form.
Despite the claims by some that they can eat raw potatoes without any problems, imho white potatoes are not paleo, because they cannot be eaten raw.
This is an interesting article I found about why they might actually be a good idea to include in your diet. I wouldnt say daily, but there is no reason to be afraid of them as long as you are cooking real whole potatos(french fries dont count)