Ancora più strano, in gestione applicazioni iio ho l'app Google play store fra le applicazioni normali, non quelle di sistema a cui accedi con il tap sui 3 puntini in alto a destra e ancora tap su mostra applicazioni di sistema.
Il tuo note 4 è versione europea o asiatica che potrebbe avere firmware in parte diverso? Nel caso cerca l'app Google play store fra quelle di sistema, quando la trovi tocchi sul tasto disattiva e ti chiede se vuoi riportarla alle impostazioni di fabbrica. Una volta disattivata, tocca su attiva e reinstalla l'ultimo aggiornamento che ti verrà proposto per vedere se risolvi..