As someone who has looked into many "healthy" diets and cooked for several people who have similar health problems to your family, I feel where you are coming from. Sometimes I feel shackled whenever I walk into the kitchen or grocery store. A couple points:
Is the paleo diet REALLY that healthy? I'm pretty sure our ancestors actually ate roots, berries, termites, and rats, not bacon and steak (probably like bears today). I'm also pretty sure they didn't eat that much meat. One thing to remember is that the paleo diet really is a fad. Three years ago almost no one knew about it, and three years from now it will have the same derision that the Atkin's diet does today. Try to pull out the nutritional advice from the diet and leave the bacon loving, fad culture part behind (eat less carbs, eat fats, eat high quality foods, eat appropriate levels of protein, etc).
One of the reasons that everyone is focusing so hard on your diet is because you need over 500k in investments just to PAY FOR FOOD. You have significantly less than that. Food is a huge, huge portion of your take home pay.
Remember that doctors only make money if you're sick. Health bloggers only make money if you're scared of something. Almost all studies are performed by corporations, for profit, and the findings can be manipulated. As a scientist, I can tell you that studies can be manipulated to "suggest" almost anything (usually not maliciously, usually just because the people performing the study are incredibly biased). Really examine every piece of evidence you receive. My guess is that you probably are a lot tougher than you think you are. The fluroide thing PROBABLY isn't necessary.
Lastly, as an example of a lower food budget, here is what I would probably try to feed my family if they had your family's health problems: gluten free grains (sprouted or soaked, if that's your thing), all vegetables, sweet potatoes, white potatoes (they're not as bad as you think), bananas, oranges, berries (buy frozen), chicken (whole organic chicken 2.79/lb at Costco), quinoa, and occasional cuts of pork or beef. Try making hash for breakfast. It's amazing. If you're willing to develop a relationship with a local farmer (I recommend it) then you may have access to other natural, healthy foods at decent prices, like raw milk, grassfed butter, and grassfed beef and pork. With your sensitivities, I would make a new rule: nothing premade comes into this house. They sneak eggs, soy, and corn into everything these days. Plus, its cheaper usually :) BTW, I'm not super familiar with fructose malabsorption, so I just did a quick search for acceptable foods. You can leave anything out that is not ok.