I don't have a complete answer for you, just a few lines of thought...
1) Construct a dependency graph
As you consider each move each token can make, store a reference to that move with each cell it passes through.
When a later move ends in one of the marked cells, we've identified a potential new dependency: performing move B before move A can change the outcome of move A. Then you can recursively check the outcome of the modified move A...
This requires some care to ensure you don't follow cycles of mutually-exclusive moves (ie. performing move A first modifies the outcome of move B which modifies the outcome of move A... but no it doesn't, because A already happened!)
Hypothetically this could get you some savings in the event that your tokens are separated from each other, so that many of the outcomes are independent of one another (your dependency graph ends up sparsely-connected). You can separate a turn into clusters, where each cluster contains multiple mutually-affecting moves (where you need to consider order, but of a smaller subset of moves) and clusters minimally affect one another (so you can ignore order between clusters, or consider fewer ordering cases).
However, my suspicion is that mutual interactions are much more common, and that you'd be introducing a lot of complexity to the algorithm for comparatively little pruning.
2) Consider a goal-based approach
A human player won't visualize every possible move. They'll usually have a strategy in mind, like "I want to get my red token in position to do X" then they'll look for a sequence of moves that accomplish this goal, often by working backwards from the goal state and considering only interactions that move them towards it.
So if your aim is to get a reasonable-performing adversary rather than one which always finds the best possible move, structuring it around goal-seeking behaviours rather than minimax tree search may reduce your problem space to a more manageable size.
Since I don't know much about the rules of your game, I can't speculate on what your goal logic might be, and generally they require more sophisticated AI design than search-based approaches.
You can even try a hybrid approach, where you do a minimax search over a set of goals rather than individual moves, pruning goals which turn out to be unfeasible once their move sequence is examined.
3) Consider sampling
If none of the above work, a fallback is to just try to search as much of the tree as you can within your available time & performance budget. This means trying to optimize your exhaustive search inner loop as much as possible, making sure you're using your transposition table to save redundant work on intermediate states and not just final configurations.
You'll want to randomize the order in which you consider moves, to avoid biasing the AI to search moves for the first token more exhaustively than the last, for example.
Whenever you hit your limit, stop, and use the best result you've found so far. You'll likely want to frame this limit in terms of steps rather than realtime, so that players on faster machines don't have to contend with stronger AI than those closer to the minimum spec. ;)
Overall, my algorithmic spidey sense is giving me that tingly feeling that there might not be any easy shortcuts here, and that a good approximation that's achievable with clear and maintainable code and scalable performance might be a better target to aim for than a complex algorithm that's provably optimal.