Hey Spinman! First off, congratulations on starting your journey towards better health! As I'm sure you'll come to realize, the Primal diet has many different categories of followers. The common theme is avoidance of toxic food; however, many people on the diet find they do well/lose more weight with carbs while others find a low carb, low fruit, no nuts diet works best for them. Seeing as you're just starting and you have 30+ lbs to lose, I wouldn't fret over these small details. While I wouldn't recommend eating more than 2 or 3 servings of fruit or nuts a day, eliminating these foods will become more important further along your weight loss when you're looking to lose the last 10-15 lbs. So, for now, GOAL: Avoid non-primal foods like the plague; eat foods that are considered primal without worrying too much about the macronutrient breakdown. If you find you are having a hard time losing weight (or you don't feel optimal), then you can start looking at playing with your macros.
You also asked about calories. 2100 calories for a man your size is rather low, but its definitely not too low if you aren't doing super intense exercise on a regular basis. My view on calories is the following: Yes, they matter. Some people believe that you can eat upwards of 3-4k calories while still losing weight as long as the majority of calories come from fat. In my experience, (yes I tried this) you won't gain much weight BUT you will probably not feel that great and you most likely won't lose weight. However, everyone is different and many people have had weight loss success on high-calorie diets as long as they're high-fat as well. I think you're plan of 2100 calories/day will get you the fastest results.
The Leangains guy knows how to manipulate his body and he definitely is some sort of fitness genius. However, as you noticed Leangains dieters do not follow a paleo/primal diet (but it can be modified to be paleo/primal). The reason they can eat so much after workouts is because the diet is based around hormonal manipulation and muscle glycogen depletion. Also, keep in mind, a lot of "leangainers" end up gaining lean muscle but not losing too much fat which is probably a result of the amount of food they end up eating. Its a great program but it depends on your goals and should really only be done at an already low bf%. And yeah, sometimes they eat whole pizzas hahaha. Well, I hope this helped!