Є спеціальна утиліта, яка шукає такі програми. Називається Kappfinder.
Можна встановити через менеджер пакунків, або наступною командою в консолі:

sudo aptitude install kdemultimedia-kappfinder-data kappfinder

Далі натискаємо Alt+F2 і вводимо: kappfinder. Програма запуститься.
Натискаємо Шукати. Відмічаємо потрібні програми. Натискаємо застосувати. Все втрачені програми знову з'являться в меню.