They key issue is that the gauge transformation also changes the square root (at $\boldsymbol k$), for example we can choose: $$\boxed{\sqrt{f(\boldsymbol k)} \to e^{-i\phi(\boldsymbol k)} \sqrt{e^{i2\phi(\boldsymbol k)} f(\boldsymbol k)}}$$
Indeed, one needs a definition of 'square root' which is never evaluated near its branch cut, and if the original square root manages this then the above gauge-transformed one also does things smoothly. One can choose a different square root (indeed if one were forced to use the above one, then each $\delta_{\boldsymbol k}$ would be invariant, which is definitely not true). The main thing I want to point is that one at least cannot keep it unchanged in the example I gave in the OP, which resolves the paradox.
Illustration: suppose one starts with a trivial insulator where in the original gauge we have $\langle \psi^{(1)}(\boldsymbol k)|T|\psi^{(2)}(\boldsymbol k)\rangle = 1$ for all $\boldsymbol k$ and by '$\sqrt{}$' we mean the one with a branch cut at the negative real axis, i.e. $\sqrt{z} = \sqrt{|z|}\exp \left(i\frac{\arg z}{2} \right)$ where $\arg z \in (-\pi,\pi]$. I will now first show that if one does the gauge transformation of the OP, that one has to redefine the square root. Secondly, I'll show that no choice of square root can arrive at a contradiction.
If I would now perform the gauge transformation $e^{i\phi(\boldsymbol k)}$ described in the OP, then $$\left\{ \begin{array}{rcl} \langle \psi^{(1)}(\boldsymbol k)|T|\psi^{(2)}(\boldsymbol k)\rangle &\to &e^{-i\phi(\boldsymbol k)} \langle \psi^{(1)}(\boldsymbol k)|T|\psi^{(2)}(\boldsymbol k)\rangle \\
\small \sqrt{\langle \psi^{(1)}(\boldsymbol k)|T|\psi^{(2)}(\boldsymbol k)\rangle \langle \psi^{(2)}(\boldsymbol k)|T|\psi^{(1)}(\boldsymbol k)\rangle} &\to &\small \sqrt{e^{-i2\phi(\boldsymbol k)}\langle \psi^{(1)}(\boldsymbol k)|T|\psi^{(2)}(\boldsymbol k)\rangle \langle \psi^{(2)}(\boldsymbol k)|T|\psi^{(1)}(\boldsymbol k)\rangle} \end{array} \right.$$
Hence using the fact that in the original gauge $\langle \psi^{(1)}(\boldsymbol k)|T|\psi^{(2)}(\boldsymbol k)\rangle = 1$, in the new gauge we obtain:
$$\left\{ \begin{array}{rcl} \langle \psi^{(1)}(\boldsymbol k)|T|\psi^{(2)}(\boldsymbol k)\rangle &= &e^{-i\phi(\boldsymbol k)} \\
\small \sqrt{\langle \psi^{(1)}(\boldsymbol k)|T|\psi^{(2)}(\boldsymbol k)\rangle \langle \psi^{(2)}(\boldsymbol k)|T|\psi^{(1)}(\boldsymbol k)\rangle} &= &\small \sqrt{e^{-i2\phi(\boldsymbol k)}} \end{array} \right.$$
There are definitely values of $\boldsymbol k$ where $e^{-i2\phi(\boldsymbol k)}$ smoothly crosses the negative real axis (i.e. where $\phi(\boldsymbol k) \approx \frac{\pi}{2}$, cf the plot in the OP), hence my original notion of 'square root' no longer suffices. Hence I must redefine my square root. I can use the one I wrote in the box at the top of this post, but that is only one particular choice. More generally, any smooth function $\alpha(\boldsymbol k)$ defines a new square root
$$\sqrt{f(\boldsymbol k)} \to e^{-i\alpha(\boldsymbol k)} \sqrt{e^{i2\alpha(\boldsymbol k)} f(\boldsymbol k)}$$
Hence we have
$$\left\{ \begin{array}{rcl} \langle \psi^{(1)}(\boldsymbol k)|T|\psi^{(2)}(\boldsymbol k)\rangle &= &e^{-i\phi(\boldsymbol k)} \\
\small \sqrt{\langle \psi^{(1)}(\boldsymbol k)|T|\psi^{(2)}(\boldsymbol k)\rangle \langle \psi^{(2)}(\boldsymbol k)|T|\psi^{(1)}(\boldsymbol k)\rangle} &= &\small e^{-i\alpha(\boldsymbol k)}\sqrt{e^{i2(\alpha(\boldsymbol k)-\phi(\boldsymbol k))}} \end{array} \right.$$
where the $\sqrt{}$ on the right-hand side is now the one with the branch-cut at the negative real-axis. We now want to show that $(-1)^{\nu}$ is gauge invariant no matter what we choose as $\alpha(\boldsymbol k)$. The only condition this $\alpha(\boldsymbol k)$ needs to satisfy is that $e^{i2(\alpha(\boldsymbol k)-\phi(\boldsymbol k))}$ never crosses the negative real axis (because that is where the branch cut of the original square root lies). There are two qualitatively different sets of solutions to this:
- $\boxed{-\frac{\pi}{2} < \alpha(\boldsymbol k)-\phi(\boldsymbol k) < \frac{\pi}{2}}$ In that case $\sqrt{e^{i2(\alpha(\boldsymbol k)-\phi(\boldsymbol k))}} = e^{i(\alpha(\boldsymbol k)-\phi(\boldsymbol k))}$. With such a choice of $\alpha(\boldsymbol k)$, we see that in fact each $\delta_{\boldsymbol k}$ is left invariant!
- $\boxed{\frac{\pi}{2} < \alpha(\boldsymbol k)-\phi(\boldsymbol k) < \frac{3\pi}{2}}$ In that case $$\sqrt{e^{i2(\alpha(\boldsymbol k)-\phi(\boldsymbol k))}} = \exp \left( i\frac{2(\alpha(\boldsymbol k)-\phi(\boldsymbol k))-2\pi}{2} \right) = -e^{i(\alpha(\boldsymbol k)-\phi(\boldsymbol k))}$$ Hence in this case, each $\delta_{\boldsymbol k} \to - \delta_{\boldsymbol k}$
Conclusion
It is not enough to consider the quantities mentioned in the OP. And it is not enough to just choose a gauge where $|\psi^{0}(\boldsymbol k)\rangle$ and $|\psi^{1}(\boldsymbol k)\rangle$ are smooth. One in fact has to make sure that for each $\boldsymbol k$, $\sqrt{\langle \psi^{(1)}(-\boldsymbol k)|T|\psi^{(2)}(\boldsymbol k)\rangle \langle \psi^{(2)}(\boldsymbol k)|T|\psi^{(1)}(-\boldsymbol k)\rangle}$ is a smooth function. (I have inserted the minus signs here because if one lets $T$ also act on the momenta then without the minus it would be trivially zero, except at the four invariant points.) This means that if one does a gauge transformation, one might be require to shift the branch cut of the square root (in a $\boldsymbol k$-dependent way). This is in such a way that at the end of the day, $(-1)^\nu$ is invariant. Note: one such choice to resolve the paradox in the OP has the property that $\sqrt{1} = -1$ at $\boldsymbol k = (0,0)$.
But...
In the above example I showed how $\delta_{\boldsymbol k}$ is defined up to a sign. Note that the calculations I did should directly extend to the general case with minor changes. Hence this proves that $(-1)^\nu$ is gauge-invariant! However, this in fact proves that any product of two $\delta_{\boldsymbol k}$'s is gauge invariant! This is in contradiction with Kane et al. claiming that one really needs all four to have a gauge-invariant object. I am not sure what I am still overlooking?