I tried to use the Plex App on the FireTV (because its a lot nicer than the one on my Samsung Smart-TV), but unfortunately I wasn’t able to playback any video. I encountered the following message:
To fix that, go to settings and change the media profile to “enforce direct playback” (or something) and it will work. Seems my Plex server doesn’t want to serve to Android devices (my Plex server runs on a Synology box).