A ver lo que está claro que eso que cuenta cacabater no viene de serie en el S4.
Algo que tu has instalado te muestra esos anuncios a pantalla completa cuando cierras una app.
El AirPush creo que sólo sirve para la publicidad que aparece en las notificaciones, el cual no es tu caso, ya que a ti te aparece una ventana a pantalla cmpleta. Luego el AirPush considero que actualmente no sirve de nada ya que Android incorpora una función que manteniendo pulsada la notificación y dandole a "Info de la aplicación" aparece el nombre de la app que muestra dicha publicidad, incluso pudiendo desinstarla o desmarcar la opción de notificación de esa app.
Lo siguiente es que comentas que usas LuckyPatcher, eso da a entender que usas apps de pago descargadas de otras fuentes gratuitamente. Esas apps son las que mas basura llevan, desde publicidad que te aparece en cualquier lugar hasta malware.
Respondiendo a la pregunta: Desinstala todas las apps "piratas", incluido Lucky Patcher y similares. A ver que resultados da.
Por eso el compañero jopato te decía: "Busca y encontrarás". Nosotros no sabemos que has instalado y que has dejado de instalar y de donde provienen las apps que has instalado y si son faibles o no.
Yo solo se que todas las apps que tengo las descargo de Play Store, Amazon Store o Samsung Apps y nunca he tenido ningún problema de anuncios ni en notificaciones ni a pantalla completa. No se puede tener todo, apps gratis parcheadas y encima todo bonito y sin travas.