"Pairing Failed" - Can't pair Vector 3 with Garmin Connect Mobile

After a few days tying to get the pedals paired I had almost given up. A mate came round so I asked him to see if they would pair to his GCM on his mobile. No problems at all. So tried mine again - Failed. I then remembered that I had installed an older version of the app, due to reading comments on here. So I re-installed the latest version.
I noticed when he tried to connect to the pedals his Bluetooth and location services was turned off, and he used the app to turn them on.
So after re-installing the the App and turning Bluetooth and Location services off, I then opened the App and logged in, it asked if I wanted to connect a device So I did, It then asked to turn on Bluetooth and the Location services, So I did using the App. Hey presto it all connected without any issues.
So might be worth a shot. good luck

Thanks dwneilevans
For some reason that worked.

So firstly I had to disconnect all connected Bluetooth devices so they were not connected on the Bluetooth "channel" of the Android phone. Then disable Bluetooth in the Settings of the phone. Also make sure you Forget the BLE Vector on Past Connected Devices, let the App do the work instead.
Using the App, it would have detected Bluetooth settings is Off, so it prompted to Open Bluetooth. Let the App open Bluetooth settings.
And yes, it now sees the pedals.

Works!

There is a small caveat which I'm trying to figure out. After a while, the Pedals go into sleep mode. Re-spinning them, Enable/Disable Bluetooth settings, nothing would revive them. I think this is not a Bluetooth issue, but its a Pedal config because the lights on the pedal don't light up too. I'm sure if given enough "Off" time, spinning the pedals will re-ignite the Pedals to become "Alive" again. Pecular, but now its workable.

Thanks dwneilevans and Frozenlkea. Based on the proposed by them I came up with a solution that worked for me, but with fewer steps.

Had exactly same issues with Vector 3 not pairing with Google Pixel 2 Android 9, pairing would fail in the GCM app, but showed up as connected in the system BT connections list.

Basically I just removed the device from known BT connections. Here are detailed steps:

- make sure pedals are not connected via BT to the phone (in stand-by or out of range),
- in BT settings go to "Previously connected devices",
- find "V3 BLE: ####" and tap gear icon next to it,
- tap "Forget" button,
- start GCM app,
- rotate cranks couple of times,
- menu -> Devices -> Add device,
- follow the wizard.

Thanks apogodin - that worked for me. This is typical Garmin - device won't connect. Need to reset and reconnect. Doesn't just work.

I tried apgodin's steps and I did get my Vector 3's paired with my Android phone (Pixel 2, Android 9) but it never stays connected for more than a second. As soon as I try to check the pedal settings I'm disconnected again. Anyone managed to figure a way to get around this? The pedals are still on 3.5 because I haven't been able to successfully update them to 3.6 yet.

I have the same issue but with an iPhone with the latest OS firmware and latest GCM version.

I'm not able to pair them by using the code on the pedals. Which by the way are different, is it normal?

Thanks