Tras probar diversas soluciones que encontré en Internet, he conseguido emparejar el sistema de manos libres y navegación del coche con el Samsung Galaxy S6.
Lo que hice fue borrar todos los ajustes que tenía el sistema del coche en el apartado Bluetooth. En particular, borré la información de conexión de mi anterior teléfono, un Note 2, que era la que impedía el emparejamiento con el S6. Es un hecho curioso, ya que el sistema del coche admite hasta 8 teléfonos diferentes. Se ve que la información del Note 2 inducía a error al sistema cuando trataba de conectarse al S6.
Espero que si a alguien le pasa algo parecido en un coche KIA, este mensaje pueda serle de ayuda. En todo caso, gracias a todos los que habéis leído mi post.