Вам всего лишь нужно засунуть desktop файл в нужное место (обычно /usr/share/applications), а потом запустить kbuildsycoca4. Никакие XML файлы править руками не требуется.
Для отладки может пригодиться опция --menutest.
Я уже дотумкал до редактирования xml-ки с меню, нашел описание формата.
Если вписать ручками пункт — работает. Из баша тоже смогу вписать.
У меня правда чутка сложнее все. Прожка должна выполняться только для текущего пользователя, поэтому ярлык положил в ~/.local/share/applications
А вот локальное меню у меня в kubuntu 12.04 почему-то лежит в ~/.config/menus/applications-kmenuedit.menu (и такое имя файла не соответствует стандарту по идее). И вот думаю теперь как это имя файла определить…