Low carb is always best, but I'm almost positive you've got other issues going on. I think you're on the right track with intestinal dysbiosis, which has to get cleared up first. That's also probably what's driving your adrenal glands so hard, which in turn suppress thyroid function (although FIRST, make. Darn. Sure. that it's not autoimmune-related, because almost all thyroid issues ARE). Removing sugars from your diet will certainly stop feeding certain organisms, but other organisms (such as certain parasites) LOVE high-protein Iron-containing foods like beef and dark chicken meat, so a good diet alone won't kill them off.
First, get thyroid labs, including antibodies (although these ab tests are often false-negative, a positive result is definitive). And don't just test TSH, either.
Next, get your GI tested (usually a stool analysis, although most doctors will look at you funny if you mention it - try to find someone with a clue ). I wouldn't just shoot in the dark on GI issues - I don't see peoples' health return until they're cleared up (including myself), no matter what else they're doing right, and there's a LOT of overlap between symptoms of candida, other types of dysbiosis, hormonal issues, and food intolerances. Best to know for sure.
Then, of course, go completely Primal - as in, the whole lifestyle. The nutrition/dietary part ROCKS, and most of us really do need to play more. What got you (and all of us) into our mess in the first place is not only a poor diet before, but also STRESS. Stress suppresses stomach acid secretion, which then robs you of your nutrients and severely disturbs the normal healthy balance of good gut flora. Stress can be found EVERYWHERE; our society is designed for it, so fight back. Turn OFF the news. Log OFF of Facebook every once in a while. Don't talk very often with the friends or family members who love to stir up drama. Move closer to work, or work closer to home (or work FROM home). Most people don't realize what a stressful waste of a life it is to sit in traffic 2 hours every day - ugh! Lol
Hope that helps