Given a complete metric space $X$. Let $\mu^*(E)=0$ if $E$ is of Cat. I, $\mu^*(E)=1$ if $E$ is of Cat. II.
I have proved that $\mu^*$ is an outer measure.
What are the $\mu^*$-measurable sets?
I've proved that all Cat. I sets are measurable. But I found no way to prove/disprove that the Cat. II sets are measurable.
Proof of All Cat. I sets are measurable: Suppose $A$ is Cat. I, then the Carathéodory condition becomes $\mu^*(S)\ge\mu^*(S\cap A)+\mu^*(S\cap A^C)=0+\mu^*(S\cap A^C)$ which is always true (subsets of Cat I are Cat I sets), thus Cat. I sets are measurable.
There are 4 types of sets in a general space $X$ (a set is first category ($C^I$) or if not it's second category ($C^{II}$) :
In a complete space type 1 does not exist, as this would imply $X$ is first category.
You've already shown that type 2 is measurable.
Type 3. is exactly the complement of sets of type 2, so also measurable. (also easy to show directly, by the same argument as for 2).
Type 4. is not measurable as we can take $S=X$ and get a contradiction $1\ge 2$ in the Carathéodory condition.
So the measurable sets are those such that $A$ or its complement is first category (but not both as that is impossible in this situation).