Version 5.21 had removed all my paired devices.

Same here 

Remove your device from your phone BT paired devices and initialize pairing from GC.
It should solve this issue.

Thanks, works again with my Fenix. Looks like I have to do the same with all other devices when I‘m back home from work.

Doesn’t work for me

Open the Settings app for your iPhone/iPad.

Select Bluetooth.

Locate the Garmin device in this list and select circle with lowercase "i"

Select Forget This Device.

Confirm you want to forget this device.

!!! Power your iPhone/iPad off. !!!

Power your Garmin device off.

Power them both back on.

Doesn't work for me either (Fenix 6 Saphire).

Now, the device doesn't even show up under available BT devices

Im in the same position. Nothing I do fixes the issue. Please address this immediately

Confirmed.

I cannot imagine how this bug of high impact went through Garmin's internal test.

Maybe we the users should be blamed again that we do not provide enough testers to Garmin?

Phew, what an expereienc again!

And just using the app for less than a minutes, I found another bug: if you tap on "Fitness age" in Health tab, GC app freezes and after 15-20 seconds it shuts itself down.

Tried 3 times, both tapping it as the first choice after opening the app then after Weight, and after Health Snapshot.