Aplikacje widoczne w menu przechowywane są w plikach w katalogu /usr/share/applications i w plikach dotyczących konfiguracji, wskazujesz lokalizację ikonki. Taki plik wygląda mniej więcej tak.
[Desktop Entry]
Encoding=UTF-8
Name= nazwa aplikacji
Exec=ścieżka do pliku wykonywalnego aplikacji
Terminal=false
X-MultipleArgs=false
Type=Application
Icon=scieżka do ikonki jaka ma być wyświetlana w menu
Categories=kategoria menu w jakiej ma wyświetlać się aplikacja, np. akcesoria
MimeType=typ mime
Jeśli chcesz zmienić poszczególne ikonki, to edytujesz pliki, dotyczące danej aplikacji. Jeśli chcesz zmienić ikonki w całym menu, to prawdopodobnie wystarczy zmienić motyw ikon.