Solution:
We shall prove that $k(n)=6 n^{2}$.

We define the distance from a given square to a given diagonal to be the minimal number of steps needed to get from the square to the diagonal. This equals the minimal number of horizontal steps needed to do that. It also equals the minimal number of vertical steps needed to do that.

Given a configuration of tokens, we define the distance from this configuration to a given diagonal to be the sum of distances of the tokens to that diagonal.

Choose the coordinate system so that the vertices of the board have coordinates $\pm 2 n$. Place a token on each of the $n$ squares the coordinates of whose centres satisfy $x>0$ and $y-x=n$. Now complete this configuration of tokens so that it has a rotational symmetry of $90^{\circ}$ about the origin. Then we have $4 n$ tokens, one in each row, one in each column. The distance from this configuration to either diagonal is $2 n \cdot n+2 n \cdot 2 n=6 n^{2}$. Therefore, $k(n) \geq 6 n^{2}$.

Now consider any configuration satisfying the conditions of the problem. We prove that $\leq 6 n^{2}$ steps suffice even if we only allow horizontal moves. I.e., the smallest of the two distances from the given configuration to the diagonals is $\leq 6 n^{2}$. It suffices to prove that the sum of the two distances from the given configuration to the diagonals is $\leq 12 n^{2}$.

Observe that the sum of the two distances from the square with center $(x, y)$ to the two diagonals is $2 \max (|x|,|y|)$. This number can take values $1,3, \ldots, 4 n-1$. The squares where it takes a given value can be covered by two columns and two rows, so we can place at most four tokens there. Thus, the sum of the values for the $4 n$ tokens is $\leq 4((4 n-1)+(4 n-3)+\cdots+(2 n+1))=4 n \cdot 3 n=12 n^{2}$.