Autoload via composer in plugin interference

Your analysis of the problem is absolutely right. By having separate autoloaders in the theme and plugin you’ll run into conflicts and only the first one being loaded.

There is no easy and general solution to this, but if you control the whole stack the best solution probably is to put the whole site including WP under composer management and define the plugin and the theme as dependencies. Then Composer can look for a version that satisfies all requirements or warns you with an error if there is an unsolvable conflict.

The one thing you can’t have is running multiple versions simultaneously.

If you want to dig deeper this article gives a great overview of the issue:
https://inpsyde.com/en/package-management-in-wordpress-introduction-solutions