I even can't add it through the phones BT setup, its not showing up in the unpaired devices list, but sadly using the GC options don't help either as previously mentioned.
But having it in the phones list helps to connect it to the right device, otherwise it will connect randomly to any other device I own with a copy of Garmin Connect installed (to be able to access my data from other devices as well).
I even can't add it through the phones BT setup
You are not supposed to pair the device with the phone from the phone's BT screen. You have to do it from Garmin Connect. If you fear pairing other devices instead of the right one, go a few meters out of their range, or turn them off. However, once the devices are already paired with the GC Mobile app, they won't pair again, unless you remove them from GCM, first.