There is a seeming contradiction as the integrands are in fact as you described them ($\boldsymbol{\nabla} \psi ^{*} \cdot \boldsymbol{\nabla} \psi \in \mathbb{R}$ while $\psi ^{*} \nabla ^{2} \psi \in \mathbb{C}$). However, the equality is in regards to their volume integrals which can be shown to be strictly real. That is because the resulting surface terms from the integration by parts are assumed to vanish at the boundaries of the integral (basically at infinity).
Let's write the complex $\psi (x)$ as:
\begin{equation}
\psi (x) = \phi (x) + i \, \chi (x) \, , \quad \phi (x) , \chi (x) \in \mathbb{R}
\end{equation}
The real quantity you pointed out shall be:
\begin{equation}
\boldsymbol{\nabla} \psi ^{*} \cdot \boldsymbol{\nabla} \psi = (\boldsymbol{\nabla} \phi )^{2} + (\boldsymbol{\nabla} \chi )^{2}
\end{equation}
While the complex quantity is:
\begin{equation}
\psi ^{*} \nabla ^{2} \psi = \phi \nabla ^{2} \phi +i \, (\phi \nabla ^{2} \chi - \chi \nabla ^{2} \phi) + \chi \nabla ^{2} \chi
\end{equation}
The imaginary part of the latter equality can be integrated by parts:
\begin{equation}
\int i \, (\phi \nabla ^{2} \chi - \chi \nabla ^{2} \phi) \, d^{3}x = i\, \Big[\phi \mathbf{\hat{r}} \cdot \boldsymbol{\nabla} \chi - \chi \mathbf{\hat{r}} \cdot \boldsymbol{\nabla} \phi \Big]_{\mathcal{V} } + \int i \, (\boldsymbol{\nabla} \chi \cdot \boldsymbol{\nabla} \phi - \boldsymbol{\nabla} \phi \cdot \boldsymbol{\nabla} \chi) \, d^{3}x
\end{equation}
where $\Big[...\Big]_{\mathcal{V} }$ implies evaluating the argument in the brackets at the limits if the integral and $\mathbf{\hat{r}}$ the unit vector of the gradient. The integral is identically 0, so the only complex part remaining are the surface terms in the bracket. But since in your proof you implicitly assumed that either $\psi$ or $\boldsymbol{\nabla} \psi$ (or both) vanish at infinity, this follows trivially for its constituent parts $\phi$ and $\chi$. Thus the complex surface term is also 0.
EDIT:
A minor addition, we may also show the vanishing of the imaginary part of the integral using Green's theorem as mentioned in the comments. Like you said:
\begin{equation}
\int _{\mathcal{V}} (\phi \nabla ^{2} \chi - \chi \nabla ^{2} \phi) \, d^{3}x = \int _{\mathcal{V}} \boldsymbol{\nabla} \cdot (\phi \boldsymbol{\nabla} \chi - \chi \boldsymbol{\nabla} \phi) \, d^{3}x = \int _{\partial \mathcal{V}} (\phi \boldsymbol{\nabla} \chi - \chi \boldsymbol{\nabla} \phi) \cdot d\mathbf{S}
\end{equation}
In order to perform this, we initially assume a finite volume $\mathcal{V}$ so that a surface boundary $\partial \mathcal{V}$ may be defined which, again as you said, we shall send to infinity i.e. $\mathcal{V}$ becomes all of space. We therefore assume the finite $\mathcal{V}$ is a sphere with a boundary being its surface at the maximum radial distance $R$. Hence the final integral is:
\begin{equation}
\int _{0} ^{2\pi} d\varphi \int _{0} ^{\pi} \sin{\theta} \, d\theta \, (\phi \boldsymbol{\nabla} \chi - \chi \boldsymbol{\nabla} \phi) \Big |_{\rho = R} \cdot \boldsymbol{\hat{\rho}} = \int _{0} ^{2\pi} d\varphi \int _{0} ^{\pi} \sin{\theta} \, d\theta \, \left (\phi \frac{\partial \chi}{\partial \rho} - \chi \frac{\partial \phi}{\partial \rho} \right ) \Bigg |_{\rho = R}
\end{equation}
Now for all of space, send $R \rightarrow +\infty$. Thus you once again get the surface terms at infinity where either the functions themselves or their derivatives (or both) vanish:
\begin{equation}
\left (\phi \frac{\partial \chi}{\partial \rho} - \chi \frac{\partial \phi}{\partial \rho} \right ) \Bigg |_{\rho = +\infty} = 0
\end{equation}
