The unit is now changed. It seem to be pretty new thing to the dealer's electrician, since he first (after 2 hours work) reported it as mission impossible. But I kept on demanding, and finally he found a solution. I don't know what he was doing (I advised him with the info given here by BenzModz (thanks!)), but he was able to pair the unit and the car. I noticed later, that the instrument cluster doesn't yet recognize the navigation, so I need to visit at the dealer once again
Also I noticed it takes pretty long for the unit to reach the satellite fix ("cold start"). And you had to use retrofit satellite gps antenna, as the original one might need a gps splitter, or maybe eliminate the satellite from the (nonusable) Teleaid system.
And yes, the visit wasn't cheap
