Насколько я понял, чтобы не создавать путаницы кед 3 и 4 создаются разные каталоги для бинарников, которые не добавляются автоматом в $PATH. Ваш k3b лежит по пути /usr/lib/kde3/bin. По поводу меню не подскажу -- не в курсе. В крайнем случае можно создать сслыку для запуска вручную.