Found a workaround that works for me. Check this post: Plex transcoding bug on Android & Android TV - Plex Players - Plex Forum
So, if you have multiple versions of the same media (movie or series). Doesn’t matter what resolution they are. Transcoding will fail if subtitles are enabled. Ensuring there is only 1 version (emptying trash) and transcoding work. This is definitely a bug in the Android App.
Did this on 5-6 movies that never starts when transcoding and they all work now.
I’ll see if I can issue a bug report on this. As I’d like to have multiple versions of certain media.
Update:
Bug reported: [BUG] Plex transcoding with subtitles bug on Android TV - Plex Players / Streaming Devices - Plex Forum