Существует документированное «как» для этого сценария, в котором не требуется иметь исполняемый файл, используя msiexec.exe вместо собственного исполняемого файла:
Как: создать ярлык для удаления
Вы не говорите, выполняет ли ваш exe-файл что-либо кроме вызова удаления, но IMO вполне приемлемо скопировать во временную папку и оставить там исполняемый файл (и это не обязательно должен быть exe-файл, потому что вы можете вызвать Создайте на нем процесс в виде файла .tmp). Существуют стандартные инструменты для очистки временных папок (очистка диска, серверные сценарии), поэтому не беспокойтесь об этом.
Как правило, вам не нужно удалять в меню «Пуск» начиная с Windows 10 и далее. Щелчок правой кнопкой мыши на установленном приложении в любом случае вызывает удаление, и оно может даже подавить ваше.