By restricting the solution to steady, fully-developed unidirectional flow , the velocity does not depend on time or the $x$-coordinate. The only relevant length scale in the $y-$dimension is $Y_c=h$. Leaving the characteristic scale for velocity $U_c$, pressure $p_c$, and $x$-dimension $X_c$ unspecified for the moment, the reduced Navier-Stokes equation is
$$\frac{\mu U_c}{h^2}\frac{d^2 u^*}{d y^{*2}}= \frac{p_c}{X_c}\frac{\partial p^*}{\partial x^*}$$
where the dimensionless variables are $u^* = u/U_c$, $y^* = y/h$, $p^* = p/p_c$, and $x^* = x/X_c$.
Rearranging we get,
$$\tag{1}\frac{d^2 u^*}{d y^{*2}}= \frac{h^2p_c}{\mu U_cX_c}\frac{\partial p^*}{\partial x^*}= \underbrace{\frac{\rho U_c h}{\mu}}_{Re} \frac{h}{X_c} \frac{p_c}{\rho U_c^2}\frac{\partial p^*}{\partial x^*}$$
At this point the usual Reynolds number $Re = \frac{\rho U_c h}{\mu}$ appears. Ostensibly there are three independent remaining scaling parameters $U_c$, $p_c$ and $X_c$. However for this fully developed flow, the pressure gradient is assumed to be a constant $G$ independent of the spatial variables. Consequently we must have
$$\frac{\partial p}{\partial x} = \frac{p_c}{X_c}\frac{\partial p^*}{\partial x^*}=G,$$
and (1) reduces to
$$\tag{2}\frac{d^2 u^*}{d y^{*2}}= \underbrace{\frac{\rho U_c h}{\mu}}_{Re} \frac{hG}{\rho U_c^2}$$
Note that the factor $\frac{hG}{\rho U_c^2}$ is a dimensionless pressure gradient where $\rho U_c^2$, the stagnation pressure for an incompressible fluid with velocity $U_c$, is the characteristic pressure scale. Regardless there is only one remaining degree-of-freedom in the choice for $U_c$.
Depending how this velocity scale is selected, we can obtain any value we like for the Reynolds number. However, in solving the differential equation we find that the maximum velocity is attained at $y=0$ and this value is an appropriate velocity scale
$$U_c = \frac{-Gh^2}{2\mu}$$
(Alternatively, we can use the average velocity as you suggest but this only differs by a factor of $2/3$.)
Upon substituting into (2) we get
$$\frac{d^2 u^*}{d y^{*2}}= -2$$
There is no paradox or inconsistency here. We expect the RHS to involve only dimensionless parameters and in this case we get a constant because the constant pressure gradient has been incorporated into the velocity scale.