Edge 520 Bluetooth Verbindungsprobleme - Samsung Galaxy S6

Hallo Forumsgemeinde,

ich habe schon alles versucht, aber ich kann den Garmin Edge 520 nicht mit dem Handy verbinden.
Softwarestand ist 5.20 - Hardreset habe ich durchgeführt. In der Bluetooth Verbindung wird der Edge erkannt und mit einem Code bestätigt, dann folgt der Hinweis man sollte die Verbindung mit der Connect App beenden, jedoch funktioniert das nicht.
Mittlerweile habe ich schon einige Stunden mit dem Durchforsten des Internets verbracht, ich finde keine Lösung.

Das Samsung Galaxy S6 hat die Android Version: 6.0.1
Der Garmin Edge hat die aktuelle Software 5.20

Ich habe es mit einem älteren Modell (Samsung Galaxy S5) probiert, da hat es nach einiger Zeit funktioniert.
Es liegt anscheinend nicht nur am Garmin. Mit dem iPhone 6 von meiner Frau funktioniert es leider auch nicht.

Gibt es irgendetwas, was man machen kann um diese Buletooth Verbindung zu bewerkstelligen, oder muss ich den Garmin zurückschicken?

Beste Grüße!