It depends on the Hilbert space.
If I follow blindly this definition I conclude that $(L^2, L_z)$ is a CSCO, because if a fix a value of $l$ and a value of $m$ there exist a unique eigenvector (namely a unique spherical harmonic for every fixed value of $l$ and $m$)
This is true if you're considering $L^2(S^2)$, the natural Hilbert space for particles confined to the surface of a sphere. However, the Hydrogen atom lives in $L^2(\mathbb R^3) \simeq L^2(\mathbb R \times S^2)$. In the latter space, the eigenstates of fixed $l$ and $m$ are degenerate; since the hydrogen atom wavefunctions can be written $\psi_{nlm}$, clearly for a fixed $l$ and $m$ we can have many different states corresponding to an infinity of possible $n$'s.
The addition of the hydrogen atom Hamiltonian as a third commuting observable breaks this degeneracy, and so $(H,L^2,L_z)$ are a complete set of commuting observables for $L^2(\mathbb R^3)$.
Note also that if we consider the spin of the electron as well, our Hilbert space becomes $L^2(\mathbb R^3) \otimes \mathbb C^2$, and the states of fixed $n,l,m$ are now doubly degenerate. To break this degeneracy, we need to add another mutually-commuting observable such as $S_z$.
In the latter case if I add the $S_z$ operator, now the states with $(n,l,m,s_z)$ are degenerate and I can lift this degeneracy by adding $S$ resulting at the end with a C.S.C.O ? And In general I can state that the degeneracy is equal to the dimension of the Hilbert space minus the number of operators ?
The answer to both questions is no. If your Hilbert space is $L^2(\mathbb R^3)\otimes \mathbb C^2$ and you consider the observables $(H,L^2,L_z)$, then the eigenspace corresponding to some $(n,l,m)$ is two-dimensional, because a general eigenstate of $H,L^2,$ and $L_z$ would be of the form
$$\Psi_{nlm} = \psi_{nlm}(\mathbf x) \otimes\pmatrix{\alpha \\ \beta}$$
for some arbitrary $\alpha,\beta\in \mathbb C$. To lift this degeneracy, we add $S_z$ to the set. Now the most general state corresponding to e.g. $(n,l,m,+1/2)$ would be of the form
$$\Psi_{nlm\uparrow} = \psi_{nlm}(\mathbf x) \otimes \pmatrix{\alpha \\ 0 }$$
for arbitrary $\alpha\in\mathbb C$, so the corresponding eigenspace is one-dimensional. This is what we mean by non-degeneracy in this context.
The answer to your second follow-up question is also no. There's no connection between the number of operators and the dimensionality of the Hilbert space. A simple example would be the infinite dimensional Hilbert space $L^2(\mathbb R)$ equipped with harmonic oscillator Hamiltonian $H_{QHO}$. Because $H_{QHO}$ has no degeneracy, it comprises a CSCO all by itself.