Find all pairs of values that are close under Hamming distance
As stated, your approach is problematic, because if 2 bitmaps have evenly spaced differences then in any rotation, there will be differences on some high order bits.

You can generalized your approach by permuting the bit position in a more complex fashion. Indeed, if you select a random permutation of bits, then all differences between 2 bitmaps with distance $5$ will appear in the 16 low-order bits with probability better than $1/50$. So repeating a few hundred times you should find a very large proportion of your bitmap pairs. For each trial, the number of pairs to test (with the same 16 high bits) is close to $64\cdot N$ (for $N\approx 2^{22}$).

However, I would also try the following approach. Built a list of your bitmaps modified in at most 2 bit positions and sort this list. If there are collisions within this list, you have two bitmaps within distance $4$. Then enumerate all values of your initial bitmaps modified three positions and search them in the list to find pairs of bitmaps at distance $5$.
The memory cost of this approach requires storing $529\cdot N$ elements and the number of elements to search in the second phase is $4960\cdot N$.



Additional information:


The probability that $5$ differences are located in the $16$ low
order bit after a random permutation of the $32$ bit-positions is
just a quotient of two binomials:
$$ \frac{\binom{16}{5}}{\binom{32}{5}}\approx 0.0217
$$
Construction of the lists, for each element in the original list, put in the augmented list: the element itself, all elements differing in one position and all elements differing in two positions (keeping the information about the original element). The number of copies for each element is $1+32+\binom{32}{2}=529.$ Any collision within this list (detected after sort) corresponds to two original element at distance at most $4$. Note that each pair can be detected several times so you will need to remove duplicates (but this was already the case with your initial algorithm).
For the final pass, it is preferable to prune the augmented list of elements to keep only those at exact distance $2$ from their original element. Then, for each original element, create the $\binom{32}{3}=4960$ elements at distance $3$ and search them within the augmented list. Once again, you need to remove duplicates since each pair is going to be detected $\binom{5}{3}=10$ times. [With extra care, you can probably anticipate/avoid most duplicates but I am not sure whether it is worth the effort.]