This error can be caused by several issues. It appears that you have given appropriate permissions to key vault and updated the access policy to enable access to ADE. Here are a few things to check for:
Make sure that you are not affected by one of the Unsupported scenarios.
To ensure that encryption secrets don't cross regional boundaries, you must create and use a key vault that's in the same region and tenant as the VMs to be encrypted. Also, if you have enabled the firewall on the key vault, you must go to the Networking tab on the key vault and enable access to Microsoft Trusted Services.
If you are using Windows Server 2016 Server Core you need to copy the binaries from a Windows Server 2016 Data Center VM to your Server Core VM.
Hopefully this resolves your issue. If not please let me know in the comments and we can work with you directly to further investigate.
If you still have questions, please let us know in the "comments" and we would be happy to help you. Comment is the fastest way of notifying the experts.
If the answer has been helpful, we appreciate hearing from you and would love to help others who may have the same question. Accepting answers helps increase visibility of this question for other members of the Microsoft Q&A community.
Thank you for helping to improve Microsoft Q&A!