Well, gluten-free is a step toward paleo. I think of paleo as a continuum. One extreme is trying to recreate paleo in its entirety. No nut flours, no "paleo" baking, if you couldn't kill/forage it with a sharp stick you can't have it.

The other end of the spectrum allows "moderate" dairy, that's the Primal setup.

There's the "Wheat Belly" diet that is fairly close to paleo too, but uses nut flours, coconut flour, some baking, no sugars and as close to natural whole foods, with some exceptions for things like "natural", non-caloric sweeteners.

I think paleo is a spectrum. There's a lot of flexibility, or inflexibility, depending on what you like.