The thing is, though, is that restarts are relatively easy to add to any language that has well-supported structures for non-local control flow; they're just a protocol, after all. That's really what Common Lisp has which most other languages lack. Common Lisp (very intelligently, IMHO) did not conflate error handling with non-local control flow; they are different concepts and deserve to be treated independently.
Specifically, the lexcal scoping of BLOCK and TAGBODY labels and the fact that RETURN-FROM and GO will unwind the stack if necessary to get to the target label make creating something like HANDLER-BIND/RESTART-BIND relatively easy. (There is also of course THROW and CATCH [which don't really have anything to do with error handling in CL, they're just structures for dynamically-scoped stack unwinding], but I've generally found the need to create explicit labels for those less elegant than using lexical scoping. You can always use a closure if you need to store the lexicaly-bound state to be used somewhere else, and the reverse is not as easy...)
You obviously also need UNWIND-PROTECT to keep things safe when the stack unwinds, but most languages successfully manage to get that with something like try-finally (or RAII in C++'s case, even if I find it clumsy sometimes).