I have Samsung A415 and Garmin Vivoactive 4S.
Same issue, if I do loose bluetooth connection the device will get removed from paired (bluetooth devices list) and Connect App requires me to pair them again. Very annoying and almost impossible to use them normally during the day.
Also worth mentioning that the device had a hardware issue which was fixed by guarantee service and that's where the issue came up.
Try removing the device from GC, and delete also all instances of the watch you find on the BT screen of you phone. If you use more phones, or also a tablet, make sure you removed the watch from all of them. Then add the watch to Garmin Connect again, following the instructins in GC. Do not pair the watch from the BT screen of the phone!