To link VSTS to you need to give the Service Principal, which forms the Service Endpoint in VSTS, access to the Key Vault; you already know this.
What can be confusing is that you can assign the application and the service principal to have access to the key vault depending on your use case. Therefore, you must ensure that you assign the right object to the access policy.
The best way to ensure you assign the right object is to do it through Azure Powershell.
Running a signed in Azure Powershell session:
$spObjectId = Get-AzureRmAdServicePrincipal -SearchString <ServicePrincipalName> | Foreach-Object {$_.Id}
Set-AzureRmKeyVaultAccessPolicy -VaultName <VaultName> -ObjectId $spObjectId -PermissionsToSecrets Get,Set
If you wanted to see further details (objectids, permissions etc) of the access policies you can get these through Powershell also:
Get-AzureRmKeyVault -VaultName <VaultName> | Foreach-Object {$_.AccessPolicies}