The BT stack is bit odd - there's a pairing sequence that is initiated when 2 devices have to pair, and sometimes the timing of this results in failure.
Here's what I recommend you do -
- If you have ever connected the Samsung S5 to this car before, try removing the link first. Also remove all other phones listed there which are no longer in use and make sure that there is at least 1 space available to store a new phone
- If the phone was removed in step above, switch off and restart the car (just ACC mode is fine, no need to start the engine)
- Switch on bluetooth on phone and then 'long press' the BT icon, under paired devices, remove all that are not relevant
- Switch off BT on phone
- On car screen, from the phone menu, select add phone - this forces the car to broadcast the BT availability and wait for pin, immediately after this, turn on BT on the phone, the car device should be visible and you can try to pair it. Sometimes during this you'll get a popup on the phone stating that the car wants to pair with PIN 'XXXXX'. Depends on if the phone makes the connection or the car does. Once done, click accept on the phone first, then on the car screen
Alternatively, you may also see a message on the phone stating that the car wants to access Phonebook and messages - you'll need to allow this.