I’m having exactly the same problem. Despite resets, re-pairing, reboots, and everything else suggested online, Samsung Health only connects 2% of the time. Strangely, the Galaxy Watch softwear connects fine - but it doesn’t pass the info to Samsung Health. Unfortunately it makes my watch almost useless because I bought it for the fitness tracking functions.
Same problem. Have to turn off Bluetooth on phone. Turn back on. Open Samsung wearables. Click 3 dots. Click connect new device. Then let it re-pair. Then Samsung Health will sync again. Couple that with the limits on how much of your health data you can see, no Apple health integration other than steps.....I’m done with this watch. Here’s hoping Apple starts offering a watch that actually looks like a watch one day.