It means the proof is explanatory, i.e., that it provides a framework of thought that extends our capability to reason about related problems within our very limited cognitive envelope. Pure proofs, like purely predictive models in science, often do not provide this.
Is that particularly valuable, though? It seems like a pretty anthropic point of view to value an algorithm as more elegant just because inferior hardware is able run it.
It's been a historically valuable heuristic -- algorithms/theories that provide cognitive scaffolding allow us not only to solve related problems but reason about the limits of applicability of that theory, successively guiding discovery of new theory. Obviously our cognitive envelope doesn't just include our own brains but the tools we use, including computational ones, so it's not as if pure proof/pure prediction don't also have value for guiding discovery, but it does require a lot of ingenuity to find ways to exploit them.
