"Unpair" all Garmin devices in android Bluetooth settings. Settings >> Bluetooth >> Unpair
Do the same for any other nearby mobile devices that might have Garmin in its Bluetooth settings. A common issue for users that have a new phone or other mobile devices also paired to the same Garmin device.
Reboot your phone, restart your Garmin.
On your Garmin device place into "pairing mode." Differs per device, but usually in Settings > Phone > Pair Phone to manually enter pairing mode.
Pair using Garmin Connect Mobile app. Do not use the phone's Bluetooth settings to pair.