Garmin connect pairing and configuration fail every time.

Every time I try to connect my edge with Garmin connect app,  configuration fails and sync does not work.

(Phone and Garmin Edge are connected via Bluetooth).

I have tried everything (?).

Edge was formatted due to corrupted route file.

Software was installed via Garmin Express.

My Edge has been working fine before above.