Para eliminar, puedes hacer remove(archivo), de la librería stdio.h (cstdio en C++)
http://www.cplusplus.com/reference/cstdio/remove/

Con respecto a lo primero, puedes listar los archivos en el directorio hasta encontrarlo.
En Windows, para listar, tienes FindFirstFile y FindNextFile, de windows.h:
FindFirstFile
FindNextFile

Al listar, te darán una estructura WIN32_FIND_DATA. Sus campos, los puedes ver aquí:
WIN32_FIND_DATA
El que te interesa, el nombre, es el campo cFileName.

En la página de FindFirstFile te aparece un ejemplo de cómo usarlo. Pero bueno, aquí un resumen (Las salidas de datos están en C++):

#include <iostream>
#include <windows.h>
 
using namespace std;
 
int main(){
	char path[] = "C:\\users\\*";
	WIN32_FIND_DATA wf;
	HANDLE handle = FindFirstFile(path, &wf);
	if(handle != INVALID_HANDLE_VALUE){
		do{
			if(strcmp(wf.cFileName, ".")!=0 && strcmp(wf.cFileName, "..")!=0){
 
				// Aqui tendrás la estructura con los datos del archivo actual
				cout << wf.cFileName << endl;
 
			}
		}while( FindNextFile(handle,&wf) );
		FindClose(handle);
	}else{
		cout << "No se pudo abrir la carpeta" << endl;
	}
}

Importante que a FindFirstFile, el path que le pasas termine en "\\*" (o "/*"), sinó solo "enumerará" la propia carpeta.

En ese caso, puedes crear con el programa un batch que se encargue de borrar el programa (y luego a si mismo), y llamarlo con "system("start archivo.bat");"

¿Por código como hago que el programa generado en C independientemente de la ruta de iniciación se mueva a la carpeta temporal? Eso me ayudaría bastante para cerrar tema