<Alt>+<F2> funktioniert fast überall, zumindest auch in Gnome und Mate…
/etc/xdg/autostart/nm-applet.desktop aus
network-manager-gnome soll dafür sorgen, dass es automatisch gestartet wird, was aber benutzerspezifisch zB durch eine angepaßte Kopie
~/.config/autostart wieder deaktiviert werden kann.
Existiert bei dir etwas verdächtiges in diesem Verzeichnis?
Darüber hinaus bieten verschiedene Windowmanager und Desktopumgebungen möglicherweise noch andere Möglichkeiten den automatischen Start zu verhindern, von e17 habe ich zB in Erinnerung, dass man jedes gewünschte Programm mit so einem Autostarteintrag einzeln noch einmal aktivieren musste - also wäre es recht interessant welchen Desktop du verwendest.
Und wenn du, wie in der Signatur angegeben, KDE verwendest, stellt sich die Frage wieso du nicht lieber
plasma-nm verwendest.
In KDE verhindert vermutlich absichtlich die Zeile
dass es automatisch startet, dann könntest du die Datei
/etc/xdg/autostart/nm-applet.desktop, wie zu Beginn beschrieben, nach
~/.config/autostart kopieren und in der Kopie dann die Zeile entfernen oder auskommentieren.