Just like what happened with Darwin Project only recently, it seems Paladins is no longer playable on Linux with Steam Play.
Late last month, I wrote an article and made a video showing off just how well Paladins was working on Linux thanks to Steam Play. Here we are again, only a couple weeks later and it's now a complete dud, with it almost instantly kicking me (and confirmed by others) out of games. You might get in for a few seconds, but with 100% reproduction it will kick you pretty quickly back to the main menu.
Back when previously writing about such an issue, I did make it clear with a note about how "with multiplayer titles and Steam Play there's nothing stopping the developer adjusting their anti-cheat which could end up locking-out Linux gamers".
It's a real shame, as both myself and my Son enjoyed playing Paladins and apart from a few issues which were also present on Windows, it worked beautifully with some really great performance.
While Steam Play has opened the door to a lot of titles not officially available on Linux, it's not quite the answer to everything as some like to repeatedly claim. This is obviously going to be a repeating problem with multiplayer games, so for now, I would honestly just keep away from any game using Easy Anti-Cheat with Steam Play. I will repeat what I said when I spoke about Darwin Project, I think Valve should really note on store pages what anti-cheat systems are used to help gamers make informed decisions.
What will be interesting, is that Valve said they will be rolling out "Steam Trust" in their post about some changes coming to Steam. Perhaps if more developers use Valve's own tools when they're available, this might not be such an issue since you would expect Valve's own tools to work with Steam Play.
I've reached out to Easy Anti-Cheat, again, to see if they would like a constructive chat about it. They didn't reply last time, so hopefully they will this time.