To enable the protection on encrypted VMs (encrypted using BEK and KEK), you need to give the Azure Backup service permission to read keys and secrets from key vault.
PS C:\> Set-AzureRmKeyVaultAccessPolicy -VaultName “KeyVaultName” -ResourceGroupName “RGNameOfKeyVault” -PermissionsToKeys backup,get,list -PermissionsToSecrets get,list -ServicePrincipalName 262044b1-e2ce-469f-a196-69ab7ada62d3
PS C:\> $pol=Get-AzureRmRecoveryServicesBackupProtectionPolicy -Name “NewPolicy”
PS C:\> Enable-AzureRmRecoveryServicesBackupProtection -Policy $pol -Name “V2VM” -ResourceGroupName “RGName1”
Note
If you are using the Azure Government cloud, then use the value ff281ffe-705c-4f53-9f37-a40e6f2c68f3 for the parameter -ServicePrincipalName in Set-AzureRmKeyVaultAccessPolicy cmdlet. Aslo you may have to register resouce provider: Microsoft.RecoveryService in order for 1st PS to work correctly. Let get the name of registered and unregistered services.