I can’t tell from your log when you ate in relation to when the headaches come on.
One possibility that occurs to me is that your headaches might be occurring when your glucose levels are low, if you are prone to hypoglycemia. You can figure that out by observing if you tend to get the headaches when you haven’t eaten for a few hours or more or/and by testing your glucose levels. If that does tend to be a problem, making sure that you have protein or/and some fat with your meals and frequent meals or snacks should help. Also, trying to avoid too simple carbohydrates and sugary foods, which cause glucose levels to spike and then plummet will help.
It wouldn’t hurt to spell out the steps Alicorn should take to rule in or out a diagnosis of celiac, since the blood test isn’t completely reliable. It’s my understanding that following a gluten free diet can be challenging at first, one needs to carefully read labels. Salad dressings, sauces, etc. often contain gluten. A friend of mine bought a separate toaster for her daughter who has celiac. I suggest specifying a set time period that he should follow a gluten free diet while keeping a diary listing all foods eaten, as well as any symptoms.