Solution:

The answer is $(\mathbf{C})$. First of all, there is at least one number $a_{k}$ that is not divisible by $2$, otherwise $2$ divides $\operatorname{mcd}(a_{1}, a_{2}, a_{3}, a_{4})$. We want to prove that $a_{k}$ must have at least two distinct prime factors: indeed, if this were not the case, we would have $a_{k}=p^{s}$ for some prime $p$ and natural number $s$. But in this case, for every other number $h=1,2,3,4$, $h \neq k$, we have that $\operatorname{mcd}(a_{h}, a_{k})$ can only be a number of the form $p^{r}$, with $1<r \leq s$ (because it must be a divisor of $p^{s}$, and it is greater than $1$ by the first hypothesis). But this would imply that all four numbers are multiples of $p$, which is impossible by the second hypothesis. Therefore there is at least one number $a_{k}$ that has at least two distinct prime factors other than two, and hence it is at least $3 \cdot 5=15$. On the other hand, one verifies that the quadruple $6,10,12,15$ satisfies all the hypotheses of the problem, so $15$ is indeed the minimum we are looking for.