These steps and video seems to be the most helpful to fix this issue.
In the Garmin Connect app remove Garmin - More > Garmin Devices > select your Garmin device > Remove Device
On your iPhone go to Settings > Bluetooth > select your Garmin device > Forget This Device
If you have any other mobile devices (phones, tablets) still paired with the Garmin, also do the same there - Settings > Bluetooth > select your Garmin device > Forget This Device
Restart iPhone
Restart Garmin
Place your Garmin in pairing mode - depends on model, but usually hold MENU > select Pair Phone.
Pair using Garmin Connect, not your phone's Bluetooth settings.
