anche se la condizione è inutile non mi sembra un grosso problema... se sei proprio preoccupato dell'overhead di controllare nuovamente se tmp == "" puoi fare così:
do
{
Console.WriteLine("Inserire un numero");
tmp=Console.ReadLine();
if (tmp=="")
break;
Num = Convert.ToInt32(tmp);
if(Num%2==0)
Console.WriteLine("Il numero inserito è pari");
else
Console.WriteLine("Il numero inserito è dispari");

}
while(true);

oppure, anche se secondo me così è peggio, in questo modo:

Console.WriteLine("Inserire un numero"); tmp=Console.ReadLine();
while (tmp != "")
{
Num = Convert.ToInt32(tmp);
if(Num%2==0)
Console.WriteLine("Il numero inserito è pari");
else
Console.WriteLine("Il numero inserito è dispari");

Console.WriteLine("Inserire un numero");
tmp=Console.ReadLine();
}

mandi