How do I let end users create and manage arbitrary connections between their user account and an entity
With Entity reference, this isn't very easy, because references are fields, and the permission management you need here is hard to do on a field level. You could still do it, but it would require a significant amount of custom work.

Consider using Relation or Flag instead.

You'll most likely get a better "out of the box experience" with the Flag module, but you will get better flexibility with the Relation module.

I've tried to convince one of Flag maintainers that the Flag is a special case of the Relation module and so should be based on it, but he didn't want to add a dependency.