My husband also has/had GERD and has also had the same operation as your wife and things have to be pretty bad to have that operation at a young age. To be honest some of the symptoms kept occurring after the operation as well, which was a bit depressing. By our own experimentation, we found that any bottled sauces, and food where we were not entirely sure of the providence could cause a reaction, so we have been trialling and errorring for years.
We went primal because I had high blood sugar and I do all the cooking. So he had no choice. What was interesting particularly for him, was that food that he did not think he reacted to, he has found he works better without. As he says himself, he functions better on meat and vegetables and some fruit.
Nexium and other medication, cause problems with absorption of nutrients, so her nutrient levels will have been depleted for years, add childbirth to the mix and she is literally exhausted to her bones.
As someone else said on the home page there is a list of paleo doctors, or you could look at Chris Kresser, he does skype consults, if you like what you read there, he is also an acupuncturist, so he may have some insight on the spine issues.
Your wife really needs to do this 100%, no 80/20 for her unfortunately. I would also add that dairy (good dairy anyway) may not be a problem. I had bad breath for years, and did not drink milk, and it persisted, stopped the wheat and sugar, it was gone, unless your wife knows for sure it is a problem all bets are off with CW allergies. While you decide on doctor and testing, the best thing to do is go grain, sugar, processed foods free for 30 days. I would also add bone broth and have a read about magnesium, I found it amazing for muscle pain.
I find the youtube clip with Terri Wahls inspirational, that is what food can do. You also might find Deep Nutrition useful as well.