Ah, I hadn't considered current (assuming the gauges were low current) the low resistance gauges are an advantage in this case as they reduce the induced noise (it has to be much stronger to affect the readings).
That'a a fair distance and noise will likely be an issue, however my guess is going to be that the problem is in the 3v power supply to the
bridge. Noise such as 60hz on there is likely to be more of an issue as it isn't differential so bypass caps at the bridge may help (possibly a lot). The balance of the bridge should reduce that but perhaps not by enough.
That's also a good bet, the more bypass caps the better in general.
While it is likely too late, had you considered the hx711 chip?
If you could put this module at the bridge somehow your 10 meters of wire would have digital signals not analog and a much higher res A/D (24 bit against 10 or 12 for most micro A/Ds). Note I've only seen these on Ebay not actually used one so I don't know if they are good in reality, but Sparkfun has a breakout board and they are usually pretty careful. Another thing to try would be to move a sensor to within a foot or so of the board and see if the same 60hz noise appears without the 10 meters of cable. If it doesn't then the cable length is the issue, if it does then its board/chip/ad which helps to isolate the problem.