Would this help?
For the sake of simplicity, say that
$$
D=\begin{bmatrix}0&0\\0&\tilde{D}\end{bmatrix},
$$
where $\tilde{D}$ is an $(m-k)\times(m-k)$ nonsingular matrix (so that the leading zero block is $k\times k$).
You can "fix" the singular block by a suitable diagonal matrix and then compensate it back to the low-rank update.
Say, $\Delta=\mathrm{diag}(\delta_i)_{i=1}^k$ be a nonsingular diagonal matrix which we want to add to the leading block of $D$ to make it nonsingular.
Note that if $E_k$ are the first $k$ columns of the identity matrix then
$$
D_+=\begin{bmatrix}\Delta & 0 \\ 0 & \tilde{D}\end{bmatrix}=D+E_k\Delta E_k^T
$$
so
$$
D+XX^T=D_+-E_k\Delta E_k^T+XX^T
=D_++[E_k,X][-E_k \Delta,X]^T=:D_++YZ^T.
$$
You can apply the lemma to this matrix. If $k$ (the number of zero diagonal entries of $D$) is sufficiently small, this should not much harm the efficiency.
There are so few matrices satisfying the conditions that writing them out explicitly is probably the fastest and most reliable way of solving this. Elegant solutions are great, but if there is any kind of time pressure, it is usually best to go with the first correct solution!
$A_1=\begin{pmatrix}1&1&1\\1&0&0\\1&0&0\end{pmatrix},$
$A_2=\begin{pmatrix}0&1&1\\1&1&0\\1&0&0\end{pmatrix},$
$A_3=\begin{pmatrix}0&1&1\\1&0&0\\1&0&1\end{pmatrix},$
$A_4=\begin{pmatrix}1&0&1\\0&0&1\\1&1&0\end{pmatrix},$
$A_5=\begin{pmatrix}0&0&1\\0&1&1\\1&1&0\end{pmatrix},$
$A_6=\begin{pmatrix}0&0&1\\0&0&1\\1&1&1\end{pmatrix},$
$A_7=\begin{pmatrix}1&1&0\\1&0&1\\0&1&0\end{pmatrix},$
$A_8=\begin{pmatrix}0&1&0\\1&1&1\\0&1&0\end{pmatrix},$
$A_9=\begin{pmatrix}0&1&0\\1&0&1\\0&1&1\end{pmatrix},$
$A_{10}=\begin{pmatrix}1&1&0\\1&1&0\\0&0&1\end{pmatrix},$
$A_{11}=\begin{pmatrix}1&0&1\\0&1&0\\1&0&1\end{pmatrix},$
$A_{12}=\begin{pmatrix}1&0&0\\0&1&1\\0&1&1\end{pmatrix},$
$A_1,A_{12}$ have many solutions; $A_6,A_8,A_{10},A_{11}$ have no solutions; $A_2,A_3,A_4,A_5,A_7,A_9$ each have a unique solution.
It is easy to see whether the zero-determinant cases have 0 or many solutions because they have a repeated row. Where the rows 2 and 3 are the same there are many solutions (because we want a value 0 in each case for that component of the vector). Where one of the repeat rows is 1 we have zero solutions.
Best Answer
$2^3-2^0=7$ choices for the first row as nozero vector. Then $2^3-2^1=6$ choices for the second row vector not in the span of the first. Then $2^3-2^2=4$ choices for the third row not in the span of the first two.