Is there any language for which a perfect optimization is decidable?
Certainly not for a Turing-complete programming language, following up on D.W. and David's comments. Consider a program in this language that simulates a Turing Machine $M$ (where $M$ is hardcoded into the program) and outputs zero if $M$ halts.

When your optimizer receives such a program where $M$ halts, it must output some least-cost program that always returns zero (because the original program always returns zero). If $M$ doesn't halt, then your optimizer can output any program that runs forever (as the original program always runs forever).

OK, now let's show that your optimizer would allow us to solve the halting problem. Suppose that the statement "return zero" has cost $C$. (Thus, we know that any least-cost program that always returns zero has cost at most $C$.) Given a Turing Machine $M$, construct the program that simulates $M$ and outputs zero if $M$ halts. Feed it to the optimizer. Run the output program for up to total cost (time) $C+1$. If it has output zero, then the original program halts. If not, the original program does not halt.

...I agree with user17410's suggestion to look at the primitive recursive functions as they are likely to be able to cover most problems we want to solve practically.