Thanks for your answer Cedron! All your reasoning seems right but I rethought the question on some way that it seems I need your converse assumption, i.e. $N \geq M$, so one of the two may be wrong. Let's see if someone can spot the problem:
By definition of PD, $x R_x^{-1} x > 0\quad \forall x \in \mathbb{R}^M \setminus \{0\}$ and since $C$ is full rank $\dim (\mathcal{R}(C)) = \min(M,N)= M$, and the projection $\tilde{x} := C y \neq 0\quad \forall y \in \mathbb{R}^N \setminus \{0\}$. Hence \begin{align} \tilde{x} = 0 \Longleftrightarrow y = 0 \tag{1} \end{align} Now we can see that $\tilde{x}^* R_x^{-1} \tilde{x} > 0\quad \forall \tilde{x} \neq 0$ following from PD of $R_x^{-1}$ so using the latter and (1), \begin{align} \tilde{x}^* R_x^{-1} \tilde{x} := y^* C^* R_x^{-1} C y > 0\quad \forall y \in \mathbb{R}^N \setminus \{0\} \tag{2} \end{align} and thus $C^* R_x^{-1} C$ is PD and hence invertible.