How can you solve this "paradox"? Central potential
The general issue is that you cannot plug your equations of motion into the Lagrangian and naively expect to get the same equations of motion back out again. Why not? Let us look at your specific example.
For the usual story we start with $$ L = \frac12 m (\dot r^2 + r^2\dot\theta^2) - V(r) . $$ We find that the angular momentum, defined by $\ell=m r^2\dot\theta$, is conserved so the equation of motion for the radial coordinate is $$ m \ddot r - \frac{\ell^2}{m r^3} + \frac{\partial V}{\partial r} = 0. $$
Now, you want to plug $\ell$ back into the Lagrangian. If we do that we have $$ L = \frac12 m \left( \dot r^2 + \frac{\ell^2}{m^2 r^2} \right) - V(r). $$ Naively, if we calculate the equation of motion from this Lagrangian that we will get the opposite sign for the $\ell^2/m r^3$ term. This is not correct!
Recall that when we call $\ell$ a conserved quantity we mean it is a constant in time, that is $\dot\ell=0$. Explicitly writing out the Euler-Lagrange equations we have $$ \frac{\mathrm{d}}{\mathrm{d}t}\left[ \left( \frac{\partial L}{\partial\dot r} \right)_{r,\theta,\dot\theta} \right] - \left( \frac{\partial L}{\partial r} \right)_{\dot r,\theta,\dot\theta} = 0.$$ Here I have included the reminder that when we take partial derivatives we mean that "everything else" is held constant and what that "everything else" is. For the problem at hand note that $$ \frac{\partial\ell}{\partial r} = \frac{2\ell}{r} \ne 0 $$ so it is not a general constant. Keeping this in mind, we do get the correct equation of motion (as we must).
Craig J Copi has already given a correct answer. Here we will give another answer based on the Hamiltonian formulation.
Recall that the Lagrangian of a non-relativistic point particle in a central potential in a 2D plane reads in polar coordinates $$L~=~\frac{1}{2}m(\dot{r}^2 +r^2\dot{\theta}^2) - V(r).$$ Here the centrifugal potential $V_{\rm cf}=-\frac{1}{2}mr^2\dot{\theta}^2<0$ is negative! Note that the centrifugal potential $V_{\rm cf}$ favors (=is minimized for) large radial position $r\to \infty$, as one would expect. See also this Phys.SE post.
The momenta are then $$p_{r}~=~\frac{\partial L}{\partial \dot{r}}~=~m\dot{r}$$ and $$p_{\theta}~=~\frac{\partial L}{\partial \dot{\theta}}~=~mr^2\dot{\theta}.$$ The angular position $\theta$ is a cyclic variable, so the conjugate momentum $p_{\theta}$ (=the angular momentum) is a constant of motion.
Now deduce that the Hamiltonian is $$H~=~\frac{p_{r}^2}{2m}+\frac{p_{\theta}^2}{2mr^2}+ V(r).$$ Here the centrifugal potential $V_{\rm cf}=\frac{p_{\theta}^2}{2mr^2}>0$ is positive! Note that the centrifugal potential $V_{\rm cf}$ favors (=is minimized for) large radial position $r\to \infty$, as one would expect.