Folgendes ausführen:
export WINEPREFIX=~/.wine; find $WINEPREFIX/drive_c/ -name "*.lnk" -exec wine winemenubuilder '{}' \;
kbuildsycoca4
Evtl. dann auch noch im kmenuedit: Bearbeiten -> Systemvoreinstellungen wieder herstellen.
Quellen:
http://wiki.winehq.org/winemenubuilder
https://forum.winehq.org/viewtopic.php?t=3769