I am struggling to find an appropriate reference to see if the following relationship between permutation matrices and the Kronecker product holds.
Suppose that $P$ is a $n^2\times n^2$ permutation matrix, then do $n\times n$ permutation (or at the very least orthogonal) matrices $A$ and $B$ exist so that $P=A \otimes B$ where $\otimes$ is the Kronecker product? If not, why?
The (strong) reverse direction seems to be straightforward to prove: if $A$ and $B$ are $n\times n$ permutation matrices, then $A \otimes B$ is an $n^2 \times n^2$ permutation matrix.
There are $n!$ possible permutation matrices $A$ and $n!$ permutation matrices $B$, so there are only $(n!)^2$ big permutation matrices of form $P=A\otimes B$. This is far less than than the number of big permutation matrices $P$, which is $(n^2)!$. If $n>1$, we have $(n!)^2<(n^2)!$, so the answer to the simplest form of your question is no if $n>1$.
I don't see how relaxing $A$ and $B$ to orthogonal matrices can possibly help: for the entries in $A\otimes B$ to be all either $0$ or $1$ pretty much forces $A$ and $B$ to be "permutation" matrices with $0$ and $\pm 1$ entries, which doesn't really give you enough scope: $(n!2^n)^2<(n^2)!$ for all sufficiently big $n$, after all.