How can I sort the results of a REST API response by the title of a connected custom post type?

You can’t, WP_Query can sort by post meta value, but it can’t then use that value as a post ID, look up that post, then sort by a value on that other post.

If you had a small number of posts, it could be done by manually sorting the results with PHP.

Fundamentally, the data is not stored in a way that makes this feasible.