Prueba a conectarlo antes de enceder la consola. Desenchúfala, conecta el mando con el cable, enchufa, enciende, pulsa el botón PS y debería vincularse. No lo desconectes hasta que esté vinculado totalmente.
También hay otra solución posible, cargar el mando en otro sitio que no sea ps4 , con el cargador de un móvil, pc, lo que quieras, dejalo cargando media hora o algo así, luego la conectas con el cable a ps4 y en teoría te encenderá el mando y se vinculará.
Podría ser incluso el cable, así que cámbialo por otro para ver si ese es el problema.