As far as I know the headaches come from the protein. I haven't really gone low carb, I was just focusing on a shit load of protein and noticed I started feeling shittier the higher the protein got. Everything I get is good in quality, protein powder accounts for about 70 of my calories only. Other than that it's eggs, chicken, turkey, dairy. Carbs are Steel cut oats, bread on training days, tons of veggies, some fruit, honey and other incidental ones. Fat is nuts, nut butter, fish oil, and from milk.
My exercise plan is Onus Wunsler's version of Starting Strength with 2 assistance moves added to the end of each workout. I may add in some additional treadmill walking, but that is nothing I do regularly, typically just when I need a little time to get out of the house.