The answer is $\max(n,k^2)$$\min(n,k^2)$.
The upper estimate: rank of $n\times n$ matrix does not exceed $n$, and rank of the sum of at most $k^2$ matrices of rank 1 does not exceed $k^2$.
Example: enumerate rows and columns from 0 to $n-1$ and partition the columns from 0 to $N-1:=\max(n,k^2)$$N-1:=\min(n,k^2)$ by the value of remainder modulo $k$; partition rows from 0 to $N-1$ by the value of quotient after division by $k$. Put 1's on the main diagonal at the places $0,1,\dots,N-1$ and zeroes at other places. This matrix has rank $N$ and it satisfies your condition: each block has at most one 1.