A more specific statement of the result from the paper is:

Lemma 1 Suppose that the theory T is omega consistent with repsect to some formula P(y) and that T has a finitely axiomatizable subtheory S satisfying

(i) Each recursive relation is definable in S

(ii) For every m = 0, 1, ....,

Then each subtheory of T is of complete degree

Also:

Corallary 6 Let T be the theory ZF or any extension of ZF. If T is omega consistent with respect to the formula then the degrees of subtheories of T are exactly the complete degrees.

ETA: Is this what you were referring to in:

Is there a formal system (not talking about the standard integers, I guess)

I'm not sure, I don't see a related reply/comment. Either way, I'm not 100% sure I'm following all of the arguments in the papers, but it appears that the theories that are of intermediate degree are necessarily very unusual and complicated, and I'm not sure how feasible it would be to construct one explicitly.

ETA2: I found yet another interesting paper that seems to state that finding a natural example of a problem of intermediate degree is a long standing open problem.