The same way as with GC, set your phone in pairing mode and scan with your bluetooth , fenix 5 must appear then.
In your Garmin Connect Mobile App
--> Menu
--> Garmin Devices
--> Tap and hold down on your device (hidden options will appear)
--> Tap on "Update Connection"
This should give you instructions on pairing with the native android bluetooth system.
No! Not on my phone. That's why I asked.
I remember from my F3 that the F3 appeared during a bluethooth scan, but not with the F5. I just tried again. No show up. With or without F5 in pairing mode.
After tap and hold down on the f5 device a menue with "cancel", "remove device" "synchronisation" appears. No "update connection"....
Garmin connect, Android V3.16.1
Same here with Galaxy S7 Edge running Android 7.0 and GC version 3.16.1. No option for Update Connection.
EDIT: After reconnecting the watch to GC again (not removing and re-adding, just reconnecting) the option now shows up, but when I choose it nothing happens.