Самое просто это запустить kmenuedit и посмотреть/поправить иконку в нем. Если не помогло или интересно понять почему вылезла проблема, и как это вообще работает, то велкам в дивный мир freedesktop стандартов
Немного вводной теории.
Иконки, название программы и текст описания для меню "Пуск", и.т.п. находятся в .desktop файлах. Системные файлы лежат в /usr/share/applications пользовательские в ~/.local/share/applications Сам десктоп файл, это ini-шка с определенными полями, иконка описывается в поле Icon (кто бы мог подумать:). В этом поле записывается только имя иконки без пути и расширения.
Иконки в линухе хранятся в темах, тема это директория в /usr/share/icons. В этоий директории иконки разбросаны по поддиректориям в соответствии с размером, и назначением иконки. Имена поддиректорий не строго стандартизированы, а описаны в файле index.theme. Но в большинстве случаев они интуитивно понятны. Я встречал 2 типа поддиректорий ТЕМА/РАЗМЕР/НАЗНАЧЕНИЕ и ТЕМА/НАЗНАЧЕНИЕ/РАЗМЕР. Директория - тип иконки значения не имеет, в любом случае иконка ищется во всех типах.
Тема может наследоваться от другой (поле Inherits в index.theme), поэтому может встретиться тема в которой почти нет иконок. В случае наследования ищется иконка в конкретной теме, потом в ее родителе, потом в родителе родителя, и.т.д. Уровень наследования не ограничен.
Если иконка не найдена то ищется в fallback теме "hicolor". Если и там нет ищется в помойке /usr/share/pixmaps.
Теоретически, пути могут отличаться от тех, которые я привел, это настраивается через переменные окружения XDG_XXX смотри "XDG Base Directory Specification" благо он очень короткий.
Имя текущей темы, стандартным способом узнать нельзя, то есть совсем, никак. За это разработчикам стандарта из freedesktop, надо голову оторвать, да и не только за это. Им частенько лениво думать и они просто пишут "desktop specific", а дальше трава не расти. А как быть разработчикам сторонних программ, никого не волнует. Но к твоей проблеме это отношения не имеет.
И до кучи, меню "Пуск" строится на основе XML файлов с корявым синтаксисом и по навороченным правилам из "Desktop Menu Specification".
Для всего этого есть стандарты.