The maximum $k$ is $2n-1$.

Firstly, we show that $k \ge 2n-1$. Suppose the first entry in a row is $a$. By adding $-a$ to this row, we make the first entry 0. Similarly, we do this for each row until the first entry of each row is 0. Next, suppose the first entry in a column is $b$. By adding $-b$ to this column, we make the first entry 0. Similarly, we do this for each column until the first entry of each column is 0. Note that we do nothing in the first column, and so all $2n-1$ entries in the first row and the first column are 0.

Secondly, we show that $k \le 2n-1$. Let $(i, j)$ be the cell in row $i$ and column $j$, and let $a_{ij}$ be the entry inside $(i, j)$. Suppose we can make $2n$ entries 0 after a finite number of steps. We call the cells containing these entries special cells. We prove the following result.

Claim. There exists a sequence of indices $i_1, i_2, \dots, i_s, j_1, j_2, \dots, j_s$ such that
$$(i_1, j_1), (i_1, j_2), (i_2, j_2), (i_2, j_3), \dots, (i_s, j_s), (i_s, j_1)$$
are distinct special cells.

Proof. Consider a graph as follows. Let the vertices be the $2n$ special cells. For each row and each column, we draw an edge between any pair of adjacent vertices. If there are $r_1, r_2, \dots, r_n$ vertices in the $n$ rows, then the number of horizontal edges is at least
$$(r_1 - 1) + (r_2 - 1) + \dots + (r_n - 1) = 2n - n = n.$$
Similarly, there are at least $n$ vertical edges. Thus, we have $2n$ edges in total. It is well-known that a graph with $2n$ vertices and at least $2n$ edges consists of a cycle.

This cycle in the graph corresponds to a 'cycle' of cells in the table. If this cycle consists of three consecutive cells $(i, j), (i, j'), (i, j'')$ in the same row, then we can remove $(i, j')$ to shorten the cycle. We can do the same thing for consecutive cells in the same column. Eventually, we obtain a cycle such that the cells alternately lie in the same row and in the same column, which is exactly our claim. $\square$

Now, we choose a cycle of special cells as given by the claim. Note that the value
$$(a_{i_1 j_1} + a_{i_2 j_2} + \dots + a_{i_s j_s}) - (a_{i_1 j_2} + a_{i_2 j_3} + \dots + a_{i_s j_1}) \quad (1)$$
is unchanged after any operation. Indeed, if we add $x$ to row $i$, and there are $m$ indices among $i_1, i_2, \dots, i_s$ equal to $i$, then the value is changed by $+mx - mx = \pm 0$. The same holds for column operations. Since all the entries involved eventually become 0, the initial value of (1) must be 0.

Consider the table consisting of the numbers $2, 2^2, \dots, 2^{n^2}$ in any order. Since each number is larger than the sum of all smaller numbers, the relation (1) cannot hold for any choice of the indices. This is a contradiction. Thus, it is impossible to have at least $2n$ special cells.

Combining the two parts, we know that the maximum $k$ is $2n-1$.