Your conjecture is true over any infinite field. More generally, in the set $M_{ab}$ of $a\times b$ matrices, at most $(a-r+1)(b-r+1)$ entries must be changed to reduce the rank of a rank $r$ matrix.
For completeness I first prove the direction you mentioned. As noted, we can reorder the rows and columns of a rank $r$ matrix $A\in M_{ab}$ until it has the form
$$
A=\begin{bmatrix}X&Y\\Z&W\end{bmatrix}
$$
where $X\in M_{r-1,r-1}$ is nonsingular. By changing the $(a-r+1)(b-r+1)$ entries in $W$, we can change $A$ to
$$
\begin{bmatrix}X&Y\\Z&ZX^{-1}Y\end{bmatrix}
=\begin{bmatrix}X\\Z\end{bmatrix}
\begin{bmatrix}I&X^{-1}Y\end{bmatrix}
$$
which has rank $r-1$, as required.
For the converse I will use some algebraic geometry. "Open" and "closed" will refer to the Zariski topology. With $m=(a-r+1)(b-r+1)-1$, we must show there exists a rank $r$ matrix whose rank cannot be reduced by changing $m$ entries. Let $R_r\subseteq M_{ab}$ denote the set of matrices of rank at most $r$. Note that $R_r$ is closed. The entries of a matrix in $M_{ab}$ are indexed by the set $I=\{1,\ldots,a\}\times\{1,\ldots,b\}$. For $J\subseteq I$, consider the subspace of matrices whose $J$-entries are zero:
$$
Z_J=\{A\in M_{ab}\mid A_{ij}=0\text{ for all }(i,j)\in J\}.
$$
Changing up to $m$ entries is equivalent to adding an element of $Z_J$ for some $J$ with $|J|=ab-m$. Thus we must prove $R_r$ is not contained in
$$
\bigcup_{J\subseteq I\atop|J|=ab-m}R_{r-1}+Z_J.
$$
In fact I will show the Zariski closure of this set does not contain $R_r$. We assumed the base field $k$ is infinite, so it suffices to prove this over the algebraic closure of $k$. Therefore suppose $k$ is algebraically closed.
Recall that there is a notion of dimension for algebraic varieties, namely Krull dimension, which coincides with linear dimension for a vector space. Moreover a dominant morphism can only reduce dimension. We need a couple of facts about $R_r$: namely it is irreducible and has dimension $r(a+b-r)$. To see this, let $U\subseteq M_{ab}$ be the open set of matrices with a nonsingular top left $r\times r$ submatrix. There is an isomorphism $GL(r)\times M_{a-r,r}\times M_{r,b-r}\to U\cap R_r$ given by
$$
(X,Y,Z)\mapsto
\begin{bmatrix}X\\Y\end{bmatrix}
\begin{bmatrix}I&Z\end{bmatrix}.
$$
Thus $U\cap R_r$ is irreducible and has dimension $r^2+(a-r)r+r(b-r)=r(a+b-r)$. The image of the multiplication map $\mu:M_{ar}\times M_{rb}\to M_{ab}$ is $R_r$. Clearly $U'=\mu^{-1}(U)$ is nonempty. Since $M_{ar}\times M_{rb}$ is irreducible, we have
$$
R_r=\mu(M_{ar}\times M_{rb})=\mu(\overline{U'})=\overline{\mu(U')}\subseteq\overline{U\cap R_r}.
$$
Hence $R_r$ is irreducible with dimension $r(a+b-r)$.
For each $J\subseteq I$, consider the projection $\phi_J:M_{ab}\to M_{ab}/Z_J$. Note that the codomain is a vector space of dimension $|J|$; intuitively $\phi_J$ picks out the $J$-entries of a matrix. Let
$$
D_r=\{J\subseteq I\mid\phi_J|_{R_r}\text{ is dominant}\}.
$$
Intuitively, $J\in D_r$ means that if someone specifies the $J$ entries of a matrix, you can almost always choose the remaining entries to make a rank $r$ matrix. If $J$ belongs to $D_r$ then so does any subset of $J$. Suppose $J\in D_r\setminus D_{r-1}$ and $R_r\subseteq\overline{R_{r-1}+Z_J}$. Then
$$
\phi_J(R_r)\subseteq\phi_J(\overline{R_{r-1}+Z_J})=\overline{\phi_J(R_{r-1}+Z_J)}=\overline{\phi_J(R_{r-1})}\subsetneq M_{ab}/Z_J,
$$
contradicting $J\in D_r$. Hence $J\in D_r\setminus D_{r-1}$ implies $\overline{R_{r-1}+Z_J}$ does not contain $R_r$.
Now suppose $|J|=ab-m$. First suppose $J\in D_r$. Recall that the dimension of $R_{r-1}$ is $(r-1)(a+b-r+1)=ab-m-1<|J|$. Thus $J\notin D_{r-1}$, so $R_r\not\subseteq\overline{R_{r-1}+Z_J}$.
On the other hand, suppose $J\notin D_r$. Pick a maximal subset $J'\subseteq J$ with $J'\in D_r$. Pick $j\in J\setminus J'$ and let $J''=J'\cup\{j\}$. Then $Z_{J'}=Z_{J''}+Z_{I\setminus\{j\}}$, so $\phi_{J'}$ factors as $\psi\phi_{J''}$ for some linear map $\psi$. Note that changing a single entry of a matrix cannot increase the rank by more than $1$, so
$$
R_{r-1}+Z_{I\setminus\{j\}}\subseteq R_r.
$$
Hence
$$
\psi^{-1}(\phi_{J'}(R_{r-1}))=\phi_{J''}(R_{r-1}+Z_{I\setminus\{j\}})\subseteq\phi_{J''}(R_r).
$$
Now $J''\notin D_r$ by choice of $J'$, so $\phi_{J''}(R_r)$ is not dense. Hence $\phi_{J'}(R_{r-1})$ is not dense, so $J'\in D_r\setminus D_{r-1}$. Hence $R_r\not\subseteq\overline{R_{r-1}+Z_{J'}}$. But $Z_J\subseteq Z_{J'}$, so again $R_r\not\subseteq\overline{R_{r-1}+Z_J}$.
We have shown $R_r\not\subseteq\overline{R_{r-1}+Z_J}$ whenever $|J|=ab-m$. Since $R_r$ is irreducible, it follows that
$$
R_r\not\subseteq\bigcup_{J\subseteq I\atop|J|=ab-m}\overline{R_{r-1}+Z_J},
$$
as required.
Finally note that the conjecture is false for a finite field. Indeed a rank $2$ matrix over a field of size $q$ can only have $q+1$ distinct rows up to scalar multiple, so the rank can be reduced by changing at most $\frac{q}{q+1}n^2$ entries. This is less than $(n-1)^2$ for $n$ sufficiently large.
