My take has always been that Clojure encourages one to model state when doing so is pragmatic. The tools provided (refs, agents, atoms and vars) are in my opinion excellent. For example, using dynamic variables for error handling can be very nice. A namespace could define something like * on-network-error* which can be dynamically bind at call site. The advantage to exceptions? * on-network-error* can be a function that tries to recover from the error.

You could implement the persistent data structures even in C. Being persistent is a matter of API, not implementation. But actually, Clojure's deftype creates immutable fields by default, so you do get the Java like final semantics (that is, you can't set the fields even though they are public).

The main reason why protocols differ from interfaces in Java or type classes in Haskell is because Clojure is a dynamically typed language. Protocol inheritance would have very little value as knowing that a monad is a functor is quite useless if you don't even know if something is a monad.

Macros don't really need polymorphism. The macro can always expand to a polymorphic function call or it can pass the s-expression to a polymorphic function.

You can actually implement the sequence interface for your own types too. But it is unfortunate that it is an interface, not a protocol, and the documentation for implementing it is nowhere to be found. What is available are functor and monad abstractions, in the contrib library.