Qué son estos iconos:

Los misteriosos iconos en la pantalla de inicio o los anuncios que obstruyen la barra de notificaciones son una forma que tienen los desarrolladores de monetizar su software.

Por lo general, la mayoría de estos anuncios provienen de empresas de marketing móvil que trabajan con los desarrolladores de aplicaciones para obtener alguna forma de ganar dinero con su software para smartphones.

Hay un extenso artículo sobre este tema en TechHive:

Los anuncios móviles furtivos invaden los teléfonos Android

Qué puedes hacer:

Puedes utilizar una aplicación para escanear e identificar las posibles aplicaciones instaladas que están causando esto en tu dispositivo:

• Detector AirPush

  Se trata de una sencilla aplicación para Android que detecta otras aplicaciones instaladas que parecen utilizar marcos publicitarios de notificación conocidos y ofrece al usuario la posibilidad de desinstalarlas fácilmente.

  Si tu dispositivo tiene Android 4.1 "Jelly Bean" o superior, ya no necesitas esta aplicación. Sólo tienes que mantener pulsadas las notificaciones y tu dispositivo te dirá quién las está generando.

• Detector de complementos

  Addons Detector detecta los complementos utilizados por sus aplicaciones instaladas. Tiene todas las herramientas para encontrar anuncios de notificaciones push y anuncios de iconos.

  Si buscas la aplicación que utiliza AirPush u otras notificaciones push, puedes encontrarla fácilmente y desinstalarla.
  Además de las notificaciones push, el uso de esta aplicación es una buena manera de ver qué aplicaciones utilizan las agencias de publicidad y qué herramientas tienen integradas.

No estoy satisfecho con las aplicaciones anteriores:

Se pueden encontrar muchos más con una búsqueda de AirPush en Google Play Store.

Yo tuve el mismo problema. La forma fácil de hacerlo es eliminar todos esos iconos. Después de esto, comprueba la página por defecto en el navegador de Internet, a veces se cambia a algún sitio como Google. Ve a ajustes -> aplicaciones y busca cualquier aplicación que hayas instalado sin Google Play. Elimina todas las aplicaciones sospechosas.

Creo que ya habrás terminado con esto. :)

La respuesta genérica es que "deberías instalar una aplicación que escanee OTRAS aplicaciones en busca de módulos que muestren notificaciones de anuncios e instalen aplicaciones que no has pedido". Yo tuve este problema y lo resolví descargando un programa de este tipo y escaneando todas mis aplicaciones. Efectivamente, algo que había instalado recientemente estaba cargado de módulos que hacen estas cosas.

Si se me permite decir el nombre del programa que utilicé, se llamaba 'Addons Detector'