Constructive version of decidability?
I think the question you are trying to ask is "is computability theory constructive?". And this is an interesting question, as you may see by this discussion on the Foundations of Mathematics mailing list.

Unsurprisingly, it has been considered, since a lot of recursion theory was developed by people with constructive sensibilities and vice versa. See e.g. Besson's book and the venerable Introduction to Metamathematics. It's pretty clear that the first couple of chapters of recursion theory survive moving to a constructive setting with minimal changes: e.g. the s-n-m theorem, Rice's theorem or the Kleene recursion theorems survive unchanged.

After the first chapters though, things get a bit tougher. In particular, the higher levels of the arithmetic hierarchy are usually defined by a notion of truth. In particular, widely used theorems such as the Low Basis Theorem seem to be explicitly non-constructive.

Perhaps a more pragmatic response, though, is that these "paradoxically computable languages" are simply an idiosyncrasy, that can (and have!) been studied at great length, like non-measurable sets of reals, but that once the initial surprise has been overcome, one can move on to more interesting things.