No, "there exists a group" is not constructive, in general. You just need to prove that non-existence leads to a contradiction. The whole deal about "constructive mathematics" is to have that if you can prove something exists, you can also construct it.

I think the success of the constructive mathematics program is really debatable, but in any case I don't think it leads to more 'natural' mathematics.

(The terms used by GP are very confused and I agree with most of your reply)