>> "I read reports and testimonies of people getting better on it and athletes performing on it."
I think this is the wrong way round. When people make claims that stuff we've been eating for thousands of years (bread, cereals, grains etc.) are actually really bad for us, the burden of proof is on them.
If anyone could actually prove that wheat causes weight gain and health problems (independent of other variables), they'd be a good candidate for the next Nobel in Medicine.
Most studies I've read show that Paleo is no better or worse than a normal healthy diet. In some cases e.g. when you're an athlete, it'll be actively worse, since carbs are a basic source of fuel. [1]
On top of this, Paleo promotes some claims that are ridiculous, e.g. that burning fat for fuel == burning carbs for fuel. They have totally different consequences.
Yes, eating lots of carbs is bad for you. So is eating lots of fatty food. Loads of calories and not enough exercise means your body stores fat. That's sort of obvious, and nothing to do with any special properties that 'carbs' have.
Just eat plenty of vegetables (esp green / strongly coloured ones), and make sure you get adequate amounts of protein & carbs. To lose weight, make sure calories in < calories out. That's the general pictures studies give us.
Be extremely sceptical of anything claiming otherwise. I'm not sure why intelligent people can get so caught up in fads - such as Paleo - that are backed up by pseudo-science. My theory is that they appeal to the contrarian in us - after all, they're delightfully counter-intuitive in some ways (eating lots of steak can be good for me?!).
You've got to have contrarian ideas to be really intelligent, but not all contrarianism is good.
[1] I say this as a semi-pro runner who has tried running on a Paleo diet and found it disastrous. You cannot burn fat with the same efficiency as you can 'burn' carbs (i.e. use glycogen). It doesn't work that way. And if you still think it does, look up the diets of the top 10 athletes in basically any sport & explain to me why none of them are on Paleo.