Navigate to the directory ~/.config/dmenu-recent/ and delete the lines that are referring to the program(s) either from the background or the terminal file in that directory.
Next time you launch dmenu you will be prompted to use background or terminal for the specific program.