Not being able to connect new devices via bluetooth

I tried to connect new bluetooth headphones to my Forerunner 955, but I always get a message saying bluetooth connection failed. I thought this was only headphone-related problem, but it also happened when trying to connect to a Ski Erg rowing machine.

The first connection failed message appears almost immediately. When pressing 'retry' the loading screen takes a lot longer but to no effect. 

I have tried troubleshooting with the possible solutions from Garmin website, but it doesn't make any difference.

Any idea how to solve this issue?