Our problem seems not to be related with key vault access policies settings, but to the Azure AD app registration settings for API permissions.
In the past we added API Permission for the key vault as visible on picture below. We did not need to grant or consent something, but now when access did not work for us, we tried to "Grant Admin consent" and error message (similar to the one we have in our log) was displayed in azure portal:
The only way we found to proceed was to remove Api permission for Key Vault and grant the consent. This can be done in portal or during first authentication to our app for the administrator. After granting, we are able to proceed to our application and everything seems to be OK.
API Permission in AD app registration also changed and granted consent is visible:
Key vault access policy did not change from the picture in my previous answer above.
Anyway we have few environments created in the past, where Azure AD app registration API permissions for Key Vault is still presenting and everything works fine ...
Post, which was also helpful for us was Create KeyVault access policy for application in another Azure Active Directory