I'm a celiac and I have a slightly different take on it. I've cut out gluten, sugar, caffeine, sodium nitrites, and MSG as triggers for sinus headaches (took years of trial and error to identify them all).
First, I love hearing carnivore diet stories because I relate to them a lot. Varying symptoms, cut out some foods, drastically improved health. I lived for 23 years with sinus headaches, I had to figure out how to work through them in college. Life is so nice now that I don't want to take a drill to my forehead.
That said, I think the carnivore diet is the shotgun blast approach. I bet there are specific triggers for their symptoms that they could identify by following a strict diet (e.g. chicken and rice) and slowly reintroducing stuff.
It's an area that is drastically understudied. All the celiac papers are on gastrointestinal issues (which I had, but the sinus headaches were 50 times worse). My understanding is eating gluten while celiac causes your body to attack your small intestine, which causes deterioration. This usually leads to problems with FODMAPs. My brother has issues with lactose, and for me it was fructose.
It's hard going to something that isn't evidence backed, but sometimes the best we can do is do the experiment on ourselves. I'm tracking what I eat everyday and when I get sinus headaches. I primarily eat protein. I get 3 beef patties and 2 small chicken breasts each day from the burger place at work. The french fries and corn chips at work are safe for me to eat, so those are the carbs I get regularly. I take a vitamin C supplement. On the weekends I cook steak, and some brazilian cheese breads. There is also a brand of gluten free bread with no sugar that I really like.
I'm extremely fortunate that I work somewhere that can accommodate my diet and that I can afford meat regularly outside of that. So yea, shout out to everyone else with weird food reactions, stay strong.