You may be getting this error because you are trying to delete the application access using AppId of the application. Please make sure to use "AssignmentID" from Azure Portal which is unique ID of the specific role assignment and links the user/group and the service principal object.
Go to Azure Active Directory > Users > Select specific User > Applications > Select any application to navigate to "Assignment Details" blade.
See screenshot below -

This unique id is also available as "ObjectID" if querying application role assignments through Graph API -
https://graph.windows.net/{TenantID}/users/{UserID}/appRoleAssignments
Here is the sample output of the above API call.
"odata.metadata": "https://graph.windows.net/sasharms.onmicrosoft.com/$metadata#directoryObjects/Microsoft.DirectoryServices.AppRoleAssignment",
"value": [
{
"odata.type": "Microsoft.DirectoryServices.AppRoleAssignment",
"objectType": "AppRoleAssignment",
"objectId": "r7rDMrnDo0uCuwnosRwwzuziiF5B8s9FnsotYya5DMU",
"deletionTimestamp": null,
"creationTimestamp": "2018-05-10T14:10:49.8197813Z",
"id": "00000000-0000-0000-0000-000000000000",
"principalDisplayName": "SaurabhSharma",
"principalId": "32c3baaf-c3b9-4ba3-82bb-09e8b11c30ce",
"principalType": "User",
"resourceDisplayName": "WebAppOpenIdGraphApi",
"resourceId": "90658e39-2559-48fb-a27a-5e50cca94288"
}
This Id is ideally used for performing various operations against the application using any programmatic interfaces like PowerShell and Graph APIs.