In principle, brains are Turing complete, and this means that evolution could be much smarter.

If by "evolution being smarter" you mean things like "brains becoming intelligent, developing science, and doing genetic engineering", then yes. But it's the brains who are smart, not the evolution per se.

The evolution would still fumble around the genetic landscape, except that with brains the local landscape becomes much more complicated, something like a fractal mountain instead of the smooth hills in most of the plain. On a different terrain, the weak algorithm may produce more interesting results. That does not make the algorithm more intelligent.