The type of call/cc (which may be realized with the đđ-calculus) corresponds with Peirce's Law, which implies LEM. This answer by Pierre-Marie PĂ©drot explains how Markov's principle can be realized by the Dialectica interpretation or statically-bound exceptions.
What other axioms have a computational interpretation?
This is a very broad question. Actually, it is even a whole research area, which is a major theme of what I would call the French school of type theory. Extending the Curry-Howard isomorphism from "proof are programs" to "side-effects implement axioms" is a core principle of this community, see e.g. the works of Krivine or Herbelin.
Below is a pot-pourri of the additional logical expressivity provided by side-effects. As usual, there are two ways to understand an effect, either in direct style, i.e. as new terms and reductions added to the language, or in indirect style, i.e. as a program translation. Note that a single axiom may have various implementations that do not behave the same computationally.
A monotonous read-only global cell (i.e. the direct syle corresponding to presheaves) gives rise to a whole lot of axioms, depending on the underlying type of the cell. They are used to implement modalities, typically. This is the computational interpretation of intuitionistic forcing, so you can use it e.g. to negate CH.
Dynamic exceptions implement Markov's rule. This is literally the computational content of the Friedman's A-translation.
Delimited continuations can prove Double Negation Shift.
Threads with message passing can be also used to implement classical logic. I don't have a reference for this one, but morally to prove A âš ÂŹA you fork, in the first process you go left and wait on the shared channel, while in the second process you go right and return a function that sends its argument on the channel and dies.
When mixing presheaves with a CPS, you get Cohen's classical forcing. The resulting effect looks like a monotonous state.
As already mentioned in OP's question, Markov's principle can be realized via the Dialectica transformation. Fun fact, the computational content of the Dialectica transformation is essentially differentiable programming.
I might add more examples if they come to my mind.
It's not really axioms themselves that are nonconstructive it's the combination of axioms which cause issues with constructive interpretations.
LEM collapses a Cartesian closed category (even distributive categories) to be nonconstructive.
If you have a substructural logic (so a closed monoidal category) or more radically cointuitionistic logic (like Set^op) you can have constructive interpretations for versions of the law of excluded middle.
You can kind of think of the situation as being like exceptions or continuations can let you "observe the evaluation order of the interpreter." So you can either weaken identities (substructural logic) or ban some constructs out right.
It's not really quite an issue of there being a constructive interpretation or not. It's more an issue of there being constructive interpretations satisfying all the logical identities we want.
