Kimmel's such a dufus. There's a gluten-free pizza place near me. I ain't had any of it, because there's cheese on it, too, and cheese is not paleo - or, more personally/specifically, I have mucous and don't shit when I eat dairy. Same with gluten in general, though wheat is the world-class criminal in this case. But I'm middle of the road. My cousin and her kid were seriously ill until they eliminated gluten from their diets.
Alternatively - I met a woman last year who said she was a paleo type, but when she was in Mexico didn't have that problem with their baked goods, and she figured it had to do with them not using irradiated fertilizer. Hmm. I'd love to eat wheat again, but I haven't bothered to follow it up, cos it ain't that much a thing.