Let $S_n\times S_n$ act on $\hbox{Mat}_n(k)$, by permutation of rows and columns, i.e. $M^{(\sigma,\tau)}=P(\sigma)MP(\tau)$, where $P$ is the permutation representation. Then there is no $(\sigma,\tau)\in S_n\times S_n$ such that $M^{(\sigma,\tau)}=M^{\top}$ for all $M\in\hbox{Mat}_n(k)$, equivalently there are no permutation matrices $P$ and $Q$ such that $PMQ=M^{\top}$ for all $M$.
My proof for this fact goes roughly as follows. From the fact $\hbox{tr}(PMQ)=\hbox{tr}(M^{\top})$ we can derive that $\hbox{tr}(QPM)=\hbox{tr}(QPMQQ^{\top})=\hbox{tr}(M^{\top})=\hbox{tr}(M)$. Then it follows $PQ=I$, thus $Q=P^{\top}$. So it is enough to show that there is no permutation matrix $P$ such that $P^{\top}MP=M^{\top}$ for all $M$.
$S_n$ acts faithfully on $\hbox{Mat}_n(k)$ by conjugation. The identity $P^{\top}MP=M^{\top}$ implies that $P^{\top} M^{\top} P=M$, thus $P$ should be an involution. But it is easy to check that if $(ij)$ is a 2-cycle in the decomposition of the involution represented by $P$ then $(P^{\top}MP)_{ii}=M_{jj}$. Thus the only possibility is $P=I$, but then $P^{\top}MP=M^{\top}$ for all $M$ is impossible.
I am not quite satisfied with this proof, I feel it is more complicated than it need be. Can you find a simpler, more elementary proof of this? (possibly avoiding lengthy computations?)
Idea for an elementary proof. Let $$ M = \begin{bmatrix} 1 & 0 & \dots & 0\\ \vdots & \vdots & & \vdots \\ 1 & 0 & \dots & 0 \end{bmatrix}. $$ Permutation of the rows fixes $M$, so $S_n \times S_n$ only acts by permuting the columns. It's easy to see that none of these are the transpose of $M$.