$2n^2 - n + 1$

In each column there are at least $n$ pairs of cells with the same colour - indeed, if $c_1,c_2,\ldots,c_n$ are the amounts of cells in colours $1,2,\ldots,n$, then $c_1 + c_2 + \cdots + c_n = 2n$ and the inequality between quadratic mean and arithmetic mean bounds the number of pairs of cells of the same colour $\sum_{i=1}^n\binom{c_i}{2} = \frac{1}{2}\left(\sum_i c_i^2 - 2n\right)$ from below by $\frac{1}{2}\left(\frac{4n^2}{n} - 2n\right) = n$. In particular, the table contains at least $kn$ pairs of cells such that in each pair the two cells are in the same column. Now if we find a pair of rows for which there are $n+1$ columns which, when intersecting the two rows, give a pair of cells of the same colour, then by Pigeonhole some two columns will yield two pairs of cells, all four of the same colour, and we are done. This occurs if $kn > n\binom{2n}{2}$, i.e. $k \geq 2n^2 - n + 1$.

Consider the complete graph $K_{2n}$ on $2n$ vertices, which has $\binom{2n}{2} = 2n^2 - n$ edges. It is (kinda) well known that we can colour its edges in $2n-1$ colours so that there are no two edges with a common vertex of the same colour - equivalently, $K_{2n}$ is partitioned into $2n-1$ perfect matchings, of size $n$ each. Indeed, ordering all but one of the vertices as equally spaced on a circle and placing the remaining one at the center, for any segment $e$ from the center to a vertex colour it and all $n-1$ perpendicular segments to it in the same colour. Take any of the matchings and colour two cells in column $1$ in the same colour if and only if their indices are connected with an edge from the matching - this uses $n$ colours in total. Then for the next $n-1$ columns rotate this colouring cyclically. Do the same for the other $2n-2$ matchings, devoting $n$ columns cyclically coloured for each matching and when a pair $(i,j)$ appears that has been coloured before in the same colour, then colour it again but in a different colour.