Solution:

$k=2681$.

Proof of $k \geq 2681$ : Abel must change at least 4021 of the sums, w.l.o.g. all column sums and all but at most one row sum. To change the column sums, Abel must alter at least one entry in every column. W.l.o.g. Abel does this first and then pauses. At the moment of this pause let $n$ rows be unchanged. Thus Abel must alter an entry in $n-1$ of these rows so that the row sums can differ. W.l.o.g. Abel does this next and pauses again. For $n \geq 671$ at least 2681 entries have already been altered. Now let $n \leq 670$. A cell is called insufficient if Abel has changed its entry but no other entry of a cell in the same row or column. Since the row sum and column sum of an insufficient cell are equal, no cell may be insufficient at the end. During Abel's first pause there are at least $2011 - 2 n$ insufficient cells. By each change up to the second pause Abel can eliminate at most one of these insufficient cells (by changing an entry in the same column), and by each change after the second pause at most two insufficient cells. Hence after the second pause at least $\frac{1}{2}(2011-2 n-(n-1))$ entries must still be altered, so altogether at least $2011+(n-1)+\frac{1}{2}(2011-2 n-(n-1))=3016-\frac{n}{2} \geq 2681$.

Sketch of proof for $k \leq 2681$ : For $1 \leq m, n \leq 2011$ let the cell in row $m$ and column $n$ be denoted by $\langle m ; n\rangle$. Abel increases the entry of 2681 cells $\langle m ; n\rangle$ each by $2(m+n)+1$, namely of $\langle 2 ; 1\rangle$ as well as, for $l=1, \ldots, 670$, of $\langle 3 l-1 ; 3 l-1\rangle,\langle 3 l ; 3 l-1\rangle,\langle 3 l+1 ; 3 l\rangle$ and $\langle 3 l+1 ; 3 l+1\rangle$.