Say I have a collection $\mathcal{M}$ of distinct binary matrices $M_i$, $i = 1, \dots, \binom{k+1}{k-1}$ of size $2^{k-1} \times (k-1)$ where in each $M_i$, all rows are distinct (note: $M_i$ is not a permutation of $M_j$). For each member of this selection, I construct a new matrix $M_i' = {M_i\brack M_i}$, i.e. I staple two copies of each matrix together forming a $2^k \times (k-1)$ matrix, where each row now appears exactly twice.
Is it possible to find a column vector $\textbf{c} \in 2^k \times 1$ such that appending it to any matrix $M_i'$ results in a $2^k \times k$ matrix $M_i'' = [M_i' \ \ \textbf{c}]$ such that all rows in $M_i''$ are once again unique? I think this would be possible if we assumed $|\mathcal{M}| \leq \binom{k}{k-1}$ but not for $|\mathcal{M}| \geq \binom{k+1}{k-1}$.
Edit: I think I may have solved it but probably not as elegantly as it can be done. Will post later/tomorrow if no one has something elegant.
Because of $|\mathcal{M}| = \binom{k+1}{k-1}$, this is equivalent to finding a $2^k \times (k+1)$ matrix $M_1$ such that some $2^k \times k$ submatrix $M_1'$ has twin row copies, and then creating $M_2 = M_1 \cup \textbf{c}_{k+2}$ such that all $\binom{k+1}{k-1}$ size $2^k \times k$ submatrices $M_2'$ are simply enumerations of all vectors in $\mathbb{F}_2^k$. If such a $\textbf{c}_{k+2}$ exists, then each $M_2'$ corresponds to a linear generator matrix $G_2'$ with full rank and $\textbf{c}_{k+2}$ must correspond to a generator column $\textbf{g}_1 \in \mathbb{F}_2^k$.
So the problem reduces to finding a generator $G \in \mathbb{F}_2^{k \times (k+2)}$ such that some $k\times k$ submatrices are rank-deficient, but all submatrices that contain $\textbf{g}_1$ have full rank.
(If this reasoning does not hold so far, I will buy a banana to whoever points out the error. I'm pretty sure what follows is correct in any case.)
All columns in $G$ is contained in the span of every size $k$ column set containing $\textbf{g}_1$ and in particular we must also have $\textbf{g}_{k+1} \in $ Span$(\{\textbf{g}_1,\dots, \textbf{g}_k\}$ and $\textbf{g}_{k+2}\in $ Span$(\{\textbf{g}_1,\dots, \textbf{g}_k\}$. This means \begin{align} \textbf{g}_1 + \sum_{i=2}^k \alpha_i \textbf{g}_i= \textbf{g}_{k+1} \end{align} for some choice of $\alpha_i$. But we require $\alpha_i=1$ for all $i$ because otherwise $\textbf{g}_1$ would be a linear combination of $k-1$ other vectors. For the same reason, the weights $\alpha_i$ in \begin{align} \textbf{g}_1 + \sum_{i=2}^k \alpha_i \textbf{g}_i= \textbf{g}_{k+2} \end{align} would also need to be one. But this implies that $\textbf{g}_{k+1} = \textbf{g}_{k+2}$, which means we could take $\{\textbf{g}_1,\textbf{g}_{k+1,}\textbf{c}_{g+2}\}$ along with $k-3$ other columns as an example of a selection of $k$ columns that includes $\textbf{g}_1$ that does not have dimension $k$. Thus, our assumption that there exists a column that only partake in full-rank submatrices induces a contradiction.
Note that the case $|\mathcal{M}| = \binom{k}{k-1}$ would correspond to finding a $2^k\times (k+1)$ matrix with the same properties. The argument would not hold here because it's possible to construct such a matrix - just set $\textbf{c}_{k+1} = \textbf{c}_1\oplus \dots \oplus \textbf{c}_k$.