80 % of body composition is determined in the kitchen, strength is determined in the gym, this is appx, don't quote me and no, I don't have any studies to back it up.
Hence if you're primary goal is to loose fat, YOU HAVE TO DIAL IN YOUR EATING. Track via Fitday or some other program, every single bite you take in, give it 30 days until you get a feel for what and how much you're eating. Paleo is fine, but, you can still gain weight.
Determine your time line to reach your goal weight, post it around the house and understand, it's a battle and you need to really NOT cheat(at least for 30 days), determine your macro %%'s that work for you , then stick with it. If you want to loose 25 lbs in 5 months, well, that's 5 lbs per month, or about 1.25 per week. Sounds doable, but, you have to stay focused.
Mike O said it best, Loose weight, eat less, Gain weight eat more. See, this sounds simple and you're shaking your head, going, " I know that", well the fact is, weight gain/loose is simple stuff, but people are looking for formula's or plans to follow, way over complicating it.
Pick up the fork more, or less, you choice.
That's my 2 cents on this Sunday morning...................