If one relaxes the question to asking the row-reduction distance of arbitrary matrices over $\mathbb{F}_2$ then it can be shown that the problem is $NP$-Complete. That is, consider
RRD (Row Reduction Distance):
Input: $m\times n$ matrices $M$, $N$
over $\mathbb{F}_2$, and an integer
$k$
Output: Whether $M$ can be row-reduces
to $N$ in $\le k$ steps
The claim is that this problem RRD is $NP$-complete. It is within $NP$, so the hardness is all that remains. To do this, consider the following related problem.
MHW (Min Hamming Weight):
Input: $P\in\mathbb{F}_2^{m\times
> n}$, $b\in\mathbb{F}_2^n$, integer $k$
Output: Is $b$ expressible as a linear
combination of $\le k$ rows of $P$.
I'll first show that MHW reduces to RRD, then show that RRD is $NP$-hard. This together will show RRD is NP-hard.
Let $(P,b,k)$ be an instance of MHW. Create $M$ and $N$ as $(m+1)\times n$ matrices, where $M$ is just $P$ with the zero row appended on, and $N$ is just $P$ with the row $b$ appended on. I'll now show that $b$ is expressible as a linear combination of at most $k$ rows of $P$ iff $M$ is row-reducible to $N$ it at most $k$ steps.
The forward direction of this claim is straightforward. Now for the backward direction. Row-reduction operations over $\mathbb{F}_2$ are just "add this row to that row", or "swap this and that row". It follows that in $\le k$ row-reductions have at most $k$ "source" rows of where the additions come from. Thus, the last row of $N$ is equal to the last row of of $M$ (which is zero) plus at most $k$ other rows of $M$. This is exactly what was wanted, as the last row of $M$ is just $b$.
This completes the proof that MHW reduces to RRD.
Now let's show that MHW is NP-hard. We'll do so with:
SET-COVER
Input: Sets $S_1,\ldots,S_m\subseteq[n]$, integer
$k$,
Ouptut: Decide if $[n]$ is the union of $\le k$ of the sets $S_i$
It is know that Set-Cover is NP-complete. Here we need a slightly stronger version of this fact, where all of the sets are of constant size, and this is still NP-complete. (To see this, one first shows that 3SAT is still NP-complete when each variable appears in at most 3 clauses. Then one runs through the "standard" reduction from 3SAT to Set-Cover, and notices that all of the sets are of constant size).
Now consider a set-cover instance. Note that if we through in all subsets of each $S_i$, the answer to the cover question doesn't change. Note that we can do this as each subset is of constant size, so there aren't too many subsets to add. Thus we get
Hered-Set-Cover
Input: Let $\mathcal{S}\subseteq
> 2^{[n]}$ be a family of sets, each of
size $O(1)$, that is subset closed.
Let $k$ be an integer.
Ouptut: Decide if $[n]$ is the union
of $\le k$ of the sets from
$\mathcal{S}$.
and Hered-Set-Cover is NP-complete, as argued above. We'll now reduce Hered-Set-Cover to MHW. Take a Hered-Set-Cover instance, with the family of sets $\mathcal{S}$ and integer $k$. Suppose there are $m$ sets. Then write out $P$ to be the $m\times n$ matrx where the rows are the indicator vectors for the sets in $\mathcal{S}$. The target vector $b$ is the all ones vector, and $k$ is as in the original problem. So if $b$ is a $\le k$ linear combination of the rows, then this immediately gives the set-cover of $\le k$ sets. If there is a set-cover of $\le k$ sets, then we can always pass to subsets so that each element in the ground set is covered exactly once, and thus when we sum up the relevant vectors in $\mathcal{F}_2$ we never run into the issue that 2=0.
So really we are doing a "set-cover with odd covering at each vertex" in the MHW instance. The point is that allowing the subsets in the family makes the exact number of coverings irrelevant, and so we can assume things are covered exactly once.
It seems like there might be a more direct reduction from the problem Exact-Cover (where in set-cover we require that each element be covered exactly once). Indeed, I sort of just untangled the reductions needed to use Exact-Cover. But Exact-Cover doesn't seem exactly right, because if $b$ is a $\le k$ linear combination this doesn't immediately translate to an exact cover.
This approach doesn't seem to address the issue when $M$ and $N$ are full-rank in the RRD problem, as the reduction of MHW to RRD needs non-full-rank, and the MHW problem is solvable in polynomial time when $P$ is full rank.
