Prueba con este código:
byte[] bytes = Encoding.Default.GetBytes(nombre);
nombre = Encoding.UTF8.GetString(bytes);
Se guarda en un arreglo de bytesarreglo de bytes la codificación de cada carácter de la cadena, y posteriormente este arreglo de bytesarreglo de bytes se vuelve a convertir en texto.
Finalmente tu código quedaría así:
Console.WriteLine("¿Cuál es tu nombre?");
string nombre = Console.ReadLine();
byte[] bytes = Encoding.Default.GetBytes(nombre);
nombre = Encoding.UTF8.GetString(bytes);
Console.WriteLine($"Hola {nombre}!");
Actualización:
Cambia la codificación de la consola a Unicode:
Console.OutputEncoding = System.Text.Encoding.Unicode;
Console.InputEncoding = System.Text.Encoding.Unicode;
Prueba también a cambiar la fuente que utiliza la consola, ya que por defecto esta utiliza el tipo Consolastipo de fuente Consolas, el cual no admite ciertos caracteres, para hacer esto das clic derecho en la barra de título de la consola, seleccionas la opción propiedades y ahí escoges otro tipo de fuente.