Given $p$ primes and $g$ generator of $\Bbb Z_p$ and $h\in\Bbb Z_p$ we need to find $z$ in $g^z=h\bmod p$.
Using Legendre symbol we know $z_0=z\bmod 2$ in $z=2^tz_t+2^{t-1}z_{t-1}+\dots+2z_1+z_0$.
Let $g^2=g_1$.
Then $g^z=g_1^{\frac{z-z_0}2}g^{z_0}=h\bmod p$.
Call $\frac{z-z_0}2$ as $z_{(1)}$.
Now we need to find $z_{(1)}$ in $g_1^{z_{(1)}}=hg^{-z_0}\bmod p$.
$z_{(1)}$ has $t-1$ bits.
In general $z_{(i)}$ has $t-i$ bits and we can recursively solve in $t=O(\log p)$ arithmetic operations.
We have avoided the principal square root problem mentioned in section $4.3$ in here.
Not sure if I understand correctly, but here's my viewpoint on where you go wrong.
In the first step to obtain $z_0$, you check whether $g^z$ is a quadratic residue modulo $p$. You then reduce to $g_1^{z_{(1)}}$. From this we want to obtain the next bit, i.e. $z_1$. If we were to proceed as before, we need to check if $g_1^{z_{(1)}}$ is a quadratic residue modulo $p$. But by definition $$g_1^{z_{(1)}}=\left(g^{z_{(1)}}\right)^2,$$ so it clearly is a quadratic residue. So this step will always return $z_1=1$, which is clearly not always true.
So this is wrong, instead we could check whether $g^{z_{(1)}}=\pm\sqrt{hg^{-z_0}}$ is a quadratic residue. But then do we check for $+\sqrt{hg^{-z_0}}$ or $-\sqrt{hg^{-z_0}}$? We don't know, and it can happen that one of them is a quadratic residue, while the other is not (consider for example $\mathbb{Z}_3$).