Hi, Westroxel. I'm probably going to say some things you don't want to hear, so feel free to down vote :)
In order to get obese, you have to have eaten a hyper caloric diet consisting largely of hyper-palitable foods and other neolithic agents of disease (food toxins, broadly). In the process of consuming this crappy hyper caloric diet, you both a) increase your set point and b) invoke an adverse internal environment comprised of at least one of the following (in actuality probably 3 or more): insulin resistance, leptin resistance, increased gut permeability, food allergies, gluten intolerance, and hormonal abnormalities.
Now, the problem with mainstream/conventional dieting is it really has, until very recently, done nothing to address any of the aforementioned issues. Instead the focus is on "losing weight" via calorie restriction. For two reasons this will result in inevitable failure (both of which paleo folks hate to hear). First, if you are doing nothing to address the any of the aforementioned issues, so they will rear their ugly heads and absolutely hinder you progress and ability to fulfill your physical potential. Luckly, the paleo diet is very good at eliminating those NADs and curing many of the aforementioned problems. However, you will not cure your insulin resistance by going ketogenic- you will be masking it. If So, in that way you will not fulfill your physical potential by eating a keto-paleo diet.
Second, if you eat a hypo caloric diet consistently, your body will lose leptin sensitivity, and will go into self preservation mode by hoarding any and all calories, causing you to reduce them further and further hoarding of calories as stored body fat (because it's not going to liberate any fat or other nutrients to build and repair muscle and drop fat in the middle of a famine- fat is a reserve source of energy). Get it? Calorie restriction will make you fatter. The only way you will ever be able to eat a hyper caloric or maintenance diet is if you recomposition your body, so it builds lean muscle and drops body fat. The BEST way to do this is combined weight and HIIT training with strategic use of carbohydrates to give your body the energy to build muscle, workout out with intensity, boost leptin, and increase insulin sensitivity. Now that you're getting leaner (shedding fat and building muscle) you require even more calories because muscle burns more calories than fat. Now you keep increasing calories and you've turned yourself into a machine and metabolic furnace. Everyone on paleohacks who is eating low calorie, ketogenic diets is putting a bandaid on a bullet wound and I think will either inevitably live in misery from self starvation (speaking from experience, I know what starvation feels like and how horrible it is for your psyche and your body composition) OR from gaining the weight back and being depressed because about it. The only way to not fall into this trap is to eat a toxin free (or very low toxin diet) and eat carbohydrates to boost leptin and restore insulin sensitivity and to engage in some combination of resistance and HIIT training to increase insulin sensitivity and nutrient uptake and influence a positive overall health and hormonal balance.
Those are my views and you can take them or leave them. Anecdotally, I self-starved for a long time and was really skinny (at 58lbs, but whose counting?), but ironically fatter than I am now. Then I ate roughly 400 calories a day, once a day and workout out too. Now I eat 3500 for maintenance and can certainly eat more and gain zero body fat (it will just go to muscle or more intense workouts). I workout probably a quarter of the amount that I used to. That's just anectodatal, and in some ways overcoming anorexia is not a far cry from overcoming obesity- both are addictive, both certainly destroy leptin sensitivity, and both create adverse hormonal environments. You could just as well argue that I was one of the successfully conventional dieters in the short term...but then I got smarter :)
So, do not get discouraged by this, Get encouraged, and take it as a learning opportunity not to diet with the intention of losing weight and not to do it by reducing calories. You're already taking good steps in repairing many of the issues by eating a paleo, low NAD diet. Now you have my thoughts on the next steps to absolutely attain your physical potential and maintain it for a lifetime.
A lot of people talk about "energy balance," but really, for all intents and purposes when you're talking about a human (or animal) body it's energy utilization. Are you gonna hoard what little calories your giving yourself as fat, or are you going to liberate fat and use your calories for building lean muscle mass?
So, in a nutshell, do NOT follow conventional dieting wisdom and do NOT follow conventional paleo-dieting wisdom either. Follow a low NAD/toxin diet with sufficient calories, and put them to good use by building leptin and insulin sensitivity, as well as a positive hormonal balance. There is my rebuttal and that is the fountain of youth. I hope you do something positive with this information and make yourself an outlier.
For a guide, let's say you weigh 250lbs(?), and you think that you would make a good, lean 200lb dude. Eat the amount of calories a 200lb active dude would with the amount of body fat and muscle mass you would like to be at. Eat like him, train like him, become him. He is your future self, and do everything like he would do as if you were him...today and everyday. Be him now and he'll be you a in the future. That's how you do it, I promise.