Sometimes i use the "Run command" functionality in KDE (Alt+F2) to start a program - that's faster than clicking all the way through the menu until i found the entry and given the fact that the dialog is saving a history i usually only type one or two characters and have the full command line available. But the command history grows by and by - and sometimes i want to remove old and no longer used entries (like gaim which is pidgin now). That's not possible *ouch* at least not in the "Run command" dialog or in the preferences. The Mozilla/Firefox-way (shift+del) also does not work.
Time to descend into the personal .kde directory and dig in some config files ...
The file in question is: ~/.kde/share/config/kdesktoprc and if you open the file in your favoured editor you can see (among others) a section named "MiniCli". Remove the no longer needed items from CompletionItems and History and save the file - but take care that KDE is not changing the file in the meantime. My own background changer (which set's a new background every minute) is such a candicate - so KDE is updating this file and your saving would overwrite the file.
The changes take effect after the next login.