Milk is out if you want to do strict, Loren Cordain-style Paleo. Lots of us here do dairy. If you don't tolerate dairy well, it may make sense to cut it out, and the only way to know for "sure" is to do an elimination experiment, then add it back in.
I think the whey is the least problematic ingredient in most whey protein products. I use an unflavored, unsweetened version, to avoid artificial sweeteners, colors, and other general chemical junk that those things are often full of.
But it depends on your goals. Why do you need the whey? Are you having trouble getting enough protein from actual food? If so, I say go for it. Just pay attention to what else you're taking along with the whey, and know that some people have bad reactions to WPC and do better with WPI, but for others, both are pretty near equal, and WPC can be cheaper.