For an $n \times n$ grid, when $n = 2m + 1$, the smallest possible value of $k$ is $2m^2 + 1$; when $n = 2m$, the smallest possible value of $k$ is $2m^2 - m + 1$.

Estimate: First, let $[x]$ denote the greatest integer not exceeding $x$, and let $m = [n/2]$. Since all the common differences of the rows are distinct, we need $n \ge 2m$ distinct common differences; and since from $-m + 1$ to $m - 1$ there are only $2(m-1) + 1 = 2m - 1 < n$ numbers in total, there must be a row whose common difference is $\ge m$ or $\le -m$. Without loss of generality, suppose that row's common difference is $\ge m$, then since the leading term $\ge 1$, we have
$$\text{last term} \ge 1 + (n-1)m = \begin{cases} 2m^2 - m + 1, & \text{if } n = 2m, \\ 2m^2 + 1, & \text{if } n = 2m + 1. \end{cases}$$

Construction: First consider the case $n = 2m + 1$. Let $t = m^2 + 1$, and consider the construction
$$\begin{pmatrix} t - m^2 & \cdots & t - 2m & t - m & t & t + m & t + 2m & \cdots & t + m^2 \\ \vdots & \vdots & \vdots & \vdots & \vdots & \vdots & \vdots & \vdots & \vdots \\ t - 2m & \cdots & t - 4 & t - 2 & t & t + 2 & t + 4 & \cdots & t + 2m \\ t - m & \cdots & t - 2 & t - 1 & t & t + 1 & t + 2 & \cdots & t + m \\ t & \cdots & t & t & t & t & t & \cdots & t \\ t + m & \cdots & t + 2 & t + 1 & t & t - 1 & t - 2 & \cdots & t - m \\ t + 2m & \cdots & t + 4 & t + 2 & t & t - 2 & t - 4 & \cdots & t - 2m \\ \vdots & \vdots & \vdots & \vdots & \vdots & \vdots & \vdots & \vdots & \vdots \\ t + m^2 & \cdots & t + 2m & t + m & t & t - m & t - 2m & \cdots & t - m^2 \end{pmatrix}$$

It is easy to verify that each row is respectively an arithmetic sequence with common difference from $-m$ to $m$, and each column is also respectively an arithmetic sequence with common difference from $-m$ to $m$, and the largest number is $t + m^2 = 2m^2 + 1$.

If $n = 2m$, then consider the construction above, and remove the last row and the last column. It is easy to see that each row and each column is still an arithmetic sequence with distinct common differences, and the largest number at this time is $t + m(m-1) = 2m^2 - m + 1$.