I don't think the issue of versioning should be a concern.

The WordPress ecosystem largely doesn't support older versions and has an expectation of things being kept current and up to date.

It's nice to see this issue hasn't been forgotten. I remember having many discussions about this a long time ago, and just gave up hope on it ever being supported in core.

The proposals here look pretty good to me.

There are also issues with plugins which don't have "dependencies" per se, but which will gain extra features if other plugins are loaded. I don't think these proposals handle that scenario, but perhaps it's not a priority at this stage either. It's an important thing to factor into the architecture though, as specific support for that concept may something considered suitable for later perhaps.