Can permutation similarities change order of Kronecker products?

The matrices you are looking for are called commutation matrices, defined as the unique permutation matrix that satisfies $$K_{m,n} \cdot {\rm vec}\{A\} = {\rm vec}\{A^{\rm T}\}$$ for an arbitrary $m \times n$ matrix $A$.

It can then be shown that $K_{m,n} \cdot (A\otimes B) \cdot K_{p,q} = B \otimes A$ where $A$ is $m \times p$ and $B$ is $n \times q$. In your case, since $R_1$ and $R_2$ are square, you could have $P=K_{N,M}$, as you already observed in the special case.

The commutation matrices are introduced in [MN79] and further studied in the book [MN88], which is a pretty nice read.

[MN79] Magnus, Jan R.; Neudecker, H., The commutation matrix: Some properties and applications, Ann. Stat. 7, 381-394 (1979). ZBL0414.62040.

[MN88] Magnus, Jan R.; Neudecker, Heinz, Matrix differential calculus with applications in statistics and econometrics, Wiley Series in Probability and Mathematical Statistics. Applied Probability and Statistics. Chichester etc.: John Wiley & Sons. XVII, 393 p.; \textsterling 24.50 (1988). ZBL0651.15001.