Las últimas actualizaciones de Android wear han sido un desastre, si lees las críticas le pasa a mucha gente, yo llevo kitkat pero me salía el mismo mensaje, me descargue la versión 1.5 que debe ser la que mejor funciona (a través de aptoide) y volví a emparejar todo y de momento todo bien.