What to do, when facing the metadata deployment error: 

insufficient access rights on entity: InteractionCustomError?

To whomever might read this, I want to share how to resolve this issue, since I did not find any results online. 

I was successfully able to deploy flows that did not have Custom Error elements, but when trying to deploy a flow, which had this, I faced the above error. I was deploying via sf / sfdx CLI, not via Change Sets. 

The only reason why I found this error, was because I was trying to change the automated deploying user (CI/CD) from a system admin profile to a minimum access profile with added permission sets that allowed for deployment. 

The cause is that the deploying user was missing either:

1. View All Data (something the System Admin profile has), or
2. Manage Flows

I did not want to grant View All Data to the deploying user, but makes sense to add the Manage Flows system permission. 

While it does not make sense, that the deploying user can deploy flows without the Manage Flows permission - that in itself was quite confusing - it does make sense that one would need Manage Flows permission to in general manage flows (including the Custom Errors elements). 

I hope this helps others.