Hola hago esto:

using Microsoft.Win32.SafeHandles;
using System;
using System.Collections.Generic;
using System.Linq;
using System.Runtime.InteropServices;
using System.Text;
using System.Threading.Tasks;
 
namespace ConsoleApplication7
{
    class Program
    {
        private static readonly IntPtr HKEY_LOCAL_MACHINE = new IntPtr(-2147483646);
        [DllImport("advapi32")]
        public static extern int RegRenameKey(SafeRegistryHandle hKey, [MarshalAs(UnmanagedType.LPWStr)] string oldname,
        [MarshalAs(UnmanagedType.LPWStr)] string newname);
        static void Main(string[] args)
        {
 
            SafeRegistryHandle hKey = null;
            hKey = new SafeRegistryHandle(HKEY_LOCAL_MACHINE,true);
            RegRenameKey(hKey, "\\SOFTWARE\\Company", "\\SOFTWARE\\Compa");
            Console.ReadLine();
 
        }
    }
}

Pero no lo renombra no se porque.

Hola.

Mediante un pequeño ensayo y error no resulta nada complicado averiguar que es lo que está fallando, sin embargo no has especificado el código de error de Windows que te devuelve la función cuando la llamas, y como comprenderás esto sería el detalle más importante al estar hablando de una función indocumentada... muestra el valor de resultado de la función. De todas formas probablemente te esté devolviendo un código 161 (0xA1) ERROR_BAD_PATHNAME o 2 (0x2) ERROR_FILE_NOT_FOUND:

• http://msdn.microsoft.com/en-us/library/windows/desktop/ms681382(v=vs.85).aspx

En primera instancia estás utilizando incorrectamente la función. Estas son las cosas a tener en cuenta:

1. El segundo parámetro de la función solamente acepta una ruta relativa (no absoluta), o también el nombre de la clave.
Es decir: "SOFTWARE\Company" o "Company"

2. El último parámetro de la función solamente acepta el (nuevo) nombre de la clave, no una ruta relativa ni tampoco absoluta.
Es decir: "Company"

3. El handle de la clave de registro debe apuntar al visor de registro adecuado (x86, x64) y hacia una clave abierta con permisos de lectura y escritura.

Aquí te muestro un ejemplo funcional (me he tomado la libertad de optimizar la firma de la función y de construir la documentación):

/// ----------------------------------------------------------------------------------------------------
/// <summary>
/// Renames a registry subkey.
/// </summary>
/// ----------------------------------------------------------------------------------------------------
/// <remarks>
/// This function is not documented, however it internaly calls <c>NtRenameKey</c> function: 
/// <para></para>
/// <see href="https://msdn.microsoft.com/en-us/library/cc512138.aspx"/>
/// </remarks>
/// ----------------------------------------------------------------------------------------------------
/// <param name="hkey">
/// A handle to the source registry rootkey or subkey.
/// </param>
/// 
/// <param name="srcSubKeyPathOrName">
/// The relative path or the name of the source subkey. (eg. "SOFTWARE\My Old SubKey" or "My Old SubKey")
/// </param>
/// 
/// <param name="dstSubkeyName">
/// The destination name of the subkey. (eg. "My New SubKey")
/// </param>
/// ----------------------------------------------------------------------------------------------------
/// <returns>
/// Returns <c>0</c> (zero) if successful; otherwise, a Win32 system error code.
/// </returns>
/// ----------------------------------------------------------------------------------------------------
[Obsolete]
[DllImport("advapi32", EntryPoint = "RegRenameKey", SetLastError = false, 
CharSet = CharSet.Auto, BestFitMapping = false, ThrowOnUnmappableChar = true)]
[return: MarshalAs(UnmanagedType.U4)]
public static extern int RegRenameKey(SafeRegistryHandle hkey, 
	                              string srcSubKeyPathOrName, 
	                              string dstSubkeyName);

using System.ComponentModel;
using System.Runtime.InteropServices;
using Microsoft.Win32;
using Microsoft.Win32.SafeHandles;
 
using (RegistryKey regKey = RegistryKey.OpenBaseKey(RegistryHive.LocalMachine, RegistryView.Registry64).
                                        OpenSubKey("SOFTWARE", RegistryKeyPermissionCheck.ReadWriteSubTree)) {
 
    int result = NativeMethods.RegRenameKey(regKey.Handle, "Old SubKey Name", "New SubKey Name");
 
    if ((result != 0)) {
        throw new Win32Exception(result);
    }
 
}

Una vez aclarado y resuelto el problema, cabe mencionar un par de cosas más:

1. Estás utilizando una función indocumentada la cual a su vez está llamando intérnamente a la función NtRenameKey la cual está marcada o es propensa a ser eliminada de la API de Windows:

• https://msdn.microsoft.com/en-us/library/cc512138(v=vs.85).aspx

...Por ende, esto que intentas hacer no sería recomendable hacerlo, vaya. Si hay funciones/exports "ocultas" o indocumentadas es por que el propósito de su uso suele estar reservado al sistema operativo, no al usuario final de la API.

2. Evidéntemente estando en una plataforma tan completa y sofisticada como es .NET y su librería de clases, no es necesario recurrir a la escritura de código no administrado e inseguro para poder renombrar una clave de registro; puedes utilizar los métodos que expone la clase Microsoft.Win32.RegistryKey para hacer un renombramiento (copiar el árbol de la subclave de origen a un lugar de destino, y posteriórmente eliminar la clave de origen). El código resultante quedará más tedioso (muchas más lineas de código), pero te aportará mucho mayor control y versatilidad que lo que estás haciendo ahora mismo.

¡Saludos!