Is there a similar theory as for symmetric polynomials, that deals with polynomials on the entries of matrices that are symmetric in both dimensions?

You have touched a vast subject called invariant theory. The direct product $G=S_n\times S_n$ of two copies of the symmetric group $S_n$ on $n$ letters naturally acts on polynomials in variables $X_{ij}$, for $1\leq i,j\leq n$: if $(\gamma,\mu)\in G$ then $(\gamma,\mu)$ sends $X_{ij}$ to $X_{\gamma(i),\mu(j)}$. A nice characterisation of the ring of invariants of this action seems unlikely, as this would mean that one can in particular use it to compute full lists of invariants of bipartite graphs on $2n$ vertices, with parts of size $n$, something that is out of reach, on all accounts.

A similar setup, although for non-bipartite graphs, is discussed in the book "Computational Invariant Theory" by Derksen and Kemper.