Let's call a right diagonal a set of pixels that have coordinates $(r+a,c+a)$, where $(r,c)$ is one of the pixels on the diagonal and $a$ is an integer assuming values in some range. The difference between coordinates has the same value for all pixels lying on a diagonal: it's equal to $D=r-c$. For two right diagonals with such differences equal to $D_1$ and $D_2$, we say that the diagonals are at distance $d$ if $|D_1-D_2|=d$.

In a similar manner, let's call a left diagonal a set of pixels that have coordinates $(r+a,c-a)$. The sum of coordinates is equal to $D=r+c$ for all pixels on a left diagonal. Just as with right diagonals, two left diagonals are at distance $d$ if $|D_1-D_2|=d$.

Lemma. Distance between two pixels $(r_1,c_1)$ and $(r_2,c_2)$ is less than or equal to $d$ if and only if both the distance between the left diagonals that contain the pixels is less than or equal to $d$ and the distance between the right diagonals that contain the pixels is less than or equal to $d$.

Proof. The condition on diagonals can be written as follows:

$${\displaystyle \begin{array}{r}|(r_1-c_1)-(r_2-c_2)|\le d\\ |(r_1+c_1)-(r_2+c_2)|\le d\end{array}}$$

This is equivalent to:

$${\displaystyle \begin{array}{r}-d\le (r_1-c_1)-(r_2-c_2)\le d\\ -d\le (r_1+c_1)-(r_2+c_2)\le d\end{array}}$$

This in turn is equivalent to the following four double inequalities:

$${\displaystyle \begin{array}{r}-d\le (r_1-r_2)+(c_2-c_1)\le d\\ -d\le (r_2-r_1)+(c_1-c_2)\le d\\ -d\le (r_1-r_2)+(c_1-c_2)\le d\\ -d\le (r_2-r_1)+(c_2-c_1)\le d\end{array}}$$

Finally, this is equivalent to $|r_1-r_2|+|c_1-c_2|\le d$, where the LHS is the definition of distance between pixels. The lemma has been proven.

The algorithm then is as follows:

1. Add an instruction for each diagonal (both left and right ones) indicating whether there is a black pixel within the diagonal.
2. Add an instruction for each diagonal (both left and right ones) indicating whether there are two black pixels within the diagonal (combining OR and XOR might come in handy).
3. Using instructions from 1. and 2., for each block of $K+1$ consecutive left diagonals have an instruction that reports whether there are two black pixels within the block.
4. Do the same for right diagonals.
5. Add a gate that returns true if and only if there is at least one gate from 3. and at least one gate from 4. that both return true.
6. Repeat steps 3. — 5. for $K$ instead of $K+1$.
7. The pixels are at distance $K$ if and only if 5. reports true but 6. reports false.

The algorithm requires $\mathcal{O}(H+W)$ instructions which consume $\mathcal{O}(HW)$ inputs. Note, however, that there exist other completely different approaches with the same order of instructions and inputs used.