Note: The attacks you refer to in that thesis are structural attacks, I will consider the complexity of a brute force attack, which would be applicable to any hash function $H$ which is well designed, approximating a pseudorandom function. There are some good answers here on the complexity of the birthday attack on a hash function, which is $O(2^{n/2})$ for an $n$-bit hash output.
Let $b$ be the number of bytes and $n=8b$ be the number of bits in the output of $H.$ It seems to me that you are happy for the hex output to be "almost correct". So we should consider the $2b$ output nibbles in $\{0,1\}^4$ and say that the output is almost $f-$correct if there are up to $f$ nibbles that are different than the output you are trying to get near to. For your examples, $f=2.$
The crucial thing is to identify the size of your 'target space', which is
$$
T:=2^{4}\sum_{j=0}^f\binom{2b}{j},\quad\quad\quad\quad(1)
$$
since there are $2^4$ nibbles. Now, $T=2^4(1+2b+2b(2b-1)/2)$ or $T=2^4(1+b(2b+1))|_{b=16}=8464\approx 2^{13.05},$
which gives attack complexity (via the birthday paradox) of $$2^{(128-13.05)/2}\approx 2^{62.5}$$
for the pairwise XOR of any two outputs of the hash function to be in $T.$
However, this is not quite enough, if what you want is to be near a given fixed hash output as opposed to be near any of the outputs so far (so you want a near preimage as opposed to a near collision). If it is the latter, then proceed as below.
The probability that you miss the fixed target for $k$ randomly chosen inputs is
$$
p(f,k)\geq \left(1-\frac{T}{2^n}\right)^k =\left[\left(1-\frac{1}{2^n /T}\right)^{2^n/T}\right]^{Tk/2^n} \sim \exp[-Tk/2^n]
$$
which is only a lower bound but accurate for small $f.$ The reason we can't proceed as in the birthday paradox writing
$$
\left(1-\frac{T}{2^n}\right)\left(1-\frac{T+1}{2^n}\right)\cdots\left(1-\frac{T+k-1}{2^n}\right)
$$
for the probability is that we may be colliding with a previous hash output but this output may not be in the target set.
If we make the product $Tk=2^n,$ then we can have a probability of success of $1-e^{-1}\approx 0.63$. Since $T=2^{13.05},$ we need to perform no more than (and probably somewhat less than)
$$
2^{128-13.05}=2^{114.95}
$$
hash computations.
If you are happy with larger $f,$ then use the dominant term in (1) to obtain
$$
T\geq 2^4 b(2b-1)\cdots(2b-f+1)
$$
for a good approximation to $T$ but the direct computation of exact $T$ is not hard either.
