I had a similar problem, when looking more at the error it showed:
"Failed to set up deployment: Repository 'UpdateSiteSourceControl' operation failed with Microsoft.Web.Hosting.SourceControls.OAuthException: Bitbucket RemoveSSHKey: (404) NotFound."
In my case, I was trying to re-setup a deployment, and the SSH key in Bitbucket was causing the problem.
I eventually deleted the project Access Key, tried creating the deployment again and it worked.