810: Bluetooth Kopplung

Jetzt will ich doch glatt mal mein Edge 810 für den Urlaub mit dem Smartphone (S4 mini) von meiner Frau koppeln.
Ich kriegs aber nicht hin.

Mein Vorgehen:
Edge:
- Bluetooth->Aktivieren
- Smartphone ->koppeln
-> "Verbindung mit Telefonwird erwartet" - "Jetzt sichtbar"

Smartphone:
- Bluetooth ein, Bluetooth für andere Geräte sichtbar
- Scannen
-> "Keine Bluetooth-Geräte in der Nähe gefunden"

Mache ich etwas falsch?
Gibt es da einen Trick?