Tengo entendido que no se pueden usar comodines para Reg Query de esa manera, tendrías que hacerlo en dos pasos:
1. Busca en la Clave superior la SubClave que tiene el comodín, con /F se especifica esa SubClave
Reg Query HKLM\SOFTWARE\Classes\PackagedCom\Package /F Microsoft.SkypeApp
2. Puedes usar Find o FindStr para limpiar la salida del comando anterior y quedarte solo con la línea respuesta que te interesa
Reg Query HKLM\SOFTWARE\Classes\PackagedCom\Package /F Microsoft.SkypeApp | FindStr Microsoft.SkypeApp
Con eso ya tendrías la parte de la Clave con comodín resuelta y solo te quedaría utilizarla para encadenarla con la otra parte y quede completa, por ejemplo puedes crear un Batch para hacer la prueba primero siempre con un simple Reg Query para ver si va a trabajar bien y no malograr el registro:
For /F
%%G In ('HKLM\SOFTWARE\Classes\PackagedCom\Package /F Microsoft.SkypeApp
^| FindStr Microsoft.SkypeApp'
) Do Reg Query
%%G\Class\{776DBC8D-7347-478C-8D71-791E12EF49D8}
Si el resultado es satisfactorio ya puedes reemplazar el último Reg Query por Reg Delete:
For /F
%%G In ('HKLM\SOFTWARE\Classes\PackagedCom\Package /F Microsoft.SkypeApp
^| FindStr Microsoft.SkypeApp'
) Do Reg Delete
%%G\Class\{776DBC8D-7347-478C-8D71-791E12EF49D8} /F
Otra opción es llamar a PowerShell que es más robusto y sencillo para tu caso porque soporta comodines directamente:
Set "clave=HKLM:\SOFTWARE\Classes\PackagedCom\Package\Microsoft.SkypeApp*\Class\{776DBC8D-7347-478C-8D71-791E12EF49D8}"
PowerShell Remove-Item %clave% -Recurse
Echo La eliminacion de claves ha terminado.