Gramatical evolution doesn't result on creating good constants
It sounds like you're saying that your approach is able to effectively find the shape of the expression, but it takes it a lot longer to find the right constants.

One possible approach is to generate an expression of the correct shape using your genetic programming method, then fill in the constants using a different method.  I would recommend trying numerical optimization techniques.  Replace each constant in your expression with a symbolic value $\alpha$.  Each different constant (at each different syntactic position) gets its own symbolic value.  Then, use numerical optimization to find the value of the constants.

Example 1. For instance, consider your complex expression $x^2 + x - (\text{stuff})$.  Replace this with $x^2 + x - \alpha$ (when you have an entire subtree that contains only constants, no variables, replace the entire subtree with a single symbolic value).  We now get a function $f(x,\alpha) = x^2 + x - \alpha$.  Use the training set $(x_1,y_n),\dots,(x_n,y_n)$ to define an objective function:

$$\Phi(\alpha) = \sum_{i=1}^n (f(x_i,\alpha) - y_i)^2.$$

Finally, use numerical optimization methods to search for $\alpha$ that minimizes $\Phi(\alpha)$.  You could try gradient descent, Newton's method, or other techniques.  The value for that subtree deriving using genetic programming supplies a reasonable starting point for the search.

Example 2. In some cases, you will have more than one constant.  For instance, you might get the expression $x^2 + 2x - 3$.  Replace each constant with a symbolic value, so we get $f(x,\alpha,\beta) = x^2 + \alpha x - \beta$.  Now you can derive an objective function as above:

$$\Phi(\alpha,\beta) = \sum_{i=1}^n (f(x_i,\alpha,\beta)-y_i)^2,$$

and use optimization methods to search for $\alpha,\beta$ that minimize $\Phi(\alpha,\beta)$.