Approximately 2 months ago I decided to stop being "semi-paleo" and was finally ready to make it a permanent change in my life; so I did a Whole30, felt great and haven't looked back since... with 1 exception - frequent bad gas. At first, on the W30, I thought it was just bad gut flora, and part of my insides healing from years of back and forth healthy and unhealthy eating, but now I'm starting to wonder if I'm intolerant to certain things.
To further complicate things, I'm currently trying to gain mass cleanly with above average meat, fat and carb (on lifting days) consumption, and the inclusion of eeeevil processed protein powders.
The good news is that I'm at least sticking to egg protein (still processed) that has about 6 ingredients and no lactose or gluten. I'd say on an average lifting day I'm putting down between 3500-4200 calories, with off-days sitting between 2500-3000. I only include this last bit of information to better provide an approximate mental picture of my macro-nutrient profile.
Now, to the question! I am still 90-95% Paleo compliant (overlooking the prot. powder), having removed all legumes, dairy, gluten, sugars, processed foods, etc. from my diet, so where should I start when it comes to finding the gas-causing culprit? Nightshades? Nuts? Eggs? If I do too many, then I feel too restricted when looking up amazing new Paleo recipes to make and subsequently devour. :D And no, that's not to mean I eat quickly or interrupt digestion with lots of liquids during meals, haha.
How about a new idea? Are you consuming fruit? If so, what types? Apples, grapes, ... using honey or maple syrup?
Reason why I ask, is that recently, after having a BAD infection and being placed on 4 different antibiotics within a 2 week period, my gut reacted STRONGLY to fruits. There's this other diet, that I've seen many Paleo people do, too, called FODMAPS. It stands for Fermentable Oligo- Di- Mono- saccharides & Polyols. These saccharides and polyols are found mainly in fruits, dairy, grains and sweeteners. Well, being Paleo, the only things on the list I was eating was the fruits. I stopped fruits for two days and gas/diarrhea/bloating disappeared!! (after 2 weeks of that, it was a HUGE relief!!)... so, perhaps look at that aspect of your diet? Here's a quick link to check it out: FODMAPS listing
Do you eat any fermented foods? I'd go for sauerkraut, kimchi, and home-made goat kefir to fix the gut. 30 hour of fermentation on kefir will leave very little lactose in it. And home-made bone broth, of course.
I think eliminating each suspect food for a few days and seeing if it helps might be instructive. Eggs are really gassy for me so I suspect the egg protein might be the culprit. If I were you I'd start with eggs, then nuts, then FODMAP vegetables.