Finalmente sono riuscito a risolvere tutto.
Il cattivo funzionamento del sistema dipendeva da un virus.
Nonostante abbia l'antivirus (Avast) qualcosa era riuscito a passare.
Ho fatto la scansione con un altro antivirus (Cureit, che non richiede nemmeno di essere installato), che mi ha trovato alcuni virus.
Eliminati quelli sono tornate le icone nella barra del menu avvio.
Meno male