Randomly chosen base64 strings will almost never overlap. And comparing the efficiency of different solutions is not possible with the fuzzy specs given.

So efficiency will also depend on the nature of the real data.

My suggestions:

• for 2 same length substrings $a (tail $A) and $b (head $B) you'll get the number of missmatches $m by counting the none null bytes in ($a ^ $b)
• those mismatches have to be <= your allowed threshold $X
• (see my remarks on no feature 'bitwise' the docs don't seem to be up to date anymore°)

But you don't need to try all possible length, because only a small number of positions are likely:

• for $X=0 you only need to check those tails in $A which start with the first character $b0 in $B
• for $X=1 you also need to check those positions which start with the second character $b1 in $B (assuming $b0 was a mismatch)
• and so on for bigger $X

This should be far more efficient than your code.

updates

• You've not provided a ranking function, allowing to stop the search for different solutions.

  I.e. when is a longer overlap with one mismatch "better" than a shorter with none?

• checking base64 for incomplete matches sounds like an XY problem to me

°) euphemism for buggy

edit