That is an interesting problem. I think your conjecture is partially correct. After adding the $H_C=-\sum_pC_p$ term to the Hamiltonian, the ground state degeneracy will be reduced for sure. The remaining degeneracy can be 2-fold in some cases. But for the most general case, the degeneracy can be completely lifted, leaving unique ground state.
I think it would be easier to prove it using the loop algebra method developed in this work [Y.-Z. You and X.-G. Wen, arXiv:1204.0113] (which you may have already known). Admittedly, the constraint-counting method you mentioned is more rigorous, and is successful for the original toric code model. However for your case with $H_C$ term, after thinking for a while, I could not figure out how to count the constraints either.
Here is how the loop algebra works.
First, let us define 4 loop operators according to the above figure (red - $\sigma^x$, green - $\sigma^y$, blue - $\sigma^z$)
$$Q_1=\prod_{l\in\text{x-line}}\sigma_l^x, Q_2=\prod_{l\in\text{y-line}}\sigma_l^x,
P_1=\prod_{l\in\text{x-line}}\sigma_l^z, P_2=\prod_{l\in\text{y-line}}\sigma_l^z.$$
Assuming periodic boundary condition, the loops wind around the torus. Operators $Q_1$ and $Q_2$ measure the $\mathbb{Z}_2$ flux through the two torus holes respectively. While $P_1$ and $P_2$ are responsible to generate or to remove such fluxes (by moving a pair of $m$-excitations around the torus). In the original toric code model, the 4 degenerated ground states on the torus can be labeled by the eigen values of $Q_1$ and $Q_2$ (i.e. the fluxes through the holes), and different ground states are connected by the action of $P_1$ and $P_2$. Therefore the ground state Hilbert space is just the representation space of these loop operators.
It can be easily verified that these loop operators follows the algebra: $Q_1P_2=-P_2Q_1$, $Q_2P_1=-P_1Q_2$, $[Q_1,Q_2]=[P_1,P_2]=[Q_1,P_1]=[Q_2,P_2]=0$ (by checking the bound overlaps). The 4 loop operators can be divided into two anti-commuting pairs. To construct the representation for these operators, we start from $\{Q_1,P_2\}=0$. The anti-commutation relation requires $Q_1$ and $P_2$ to be represented by two Pauli matrices, say $Q_1\bumpeq\sigma_3$ and $P_2\bumpeq\sigma_1$. The same applies for $\{Q_2,P_1\}=0$. However the representation space must be enlarged such that the commutation relations between the anti-commuting pairs are also satisfied:
$$Q_1\bumpeq\sigma_3\otimes\sigma_0, Q_2\bumpeq\sigma_0\otimes\sigma_3, P_1\bumpeq\sigma_0\otimes\sigma_1, P_1\bumpeq\sigma_1\otimes\sigma_0.$$
For the original toric code model, it is easy to show that the Hamiltonian commutes with all the 4 loop operators, therefore it must act trivially in the representation space of loop operators, $H\bumpeq\sigma_0\otimes\sigma_0$. That is the algebraic reason that the ground states (and in fact each energy level) must be (at least) 4-fold degenerated.
Now let us consider the effect of adding $H_C$ term. All the $C_p$ operators can be divided into two classes: those away from $Q_{1,2}$ loops as $C_{p1}$ in the figure, and those adjacent to $Q_{1,2}$ loops as $C_{p2}$ in the figure. The Hamiltonian is the sum of these two classes of $C_p$ operators: $H_C=H_{1}+H_{2}$, with $H_{1,2}=-\sum C_{p1,p2}$. Note that $H_1$ commutes with all the loop operators still. However $H_2$ anti-commutes with $Q_1$ or $Q_2$ while commutes with $P_1$ and $P_2$. Therefore $H_1$ and $H_2$ are represented differently: $H_1\bumpeq\sigma_0\otimes\sigma_0$, $H_2\bumpeq a\sigma_1\otimes\sigma_0+ b\sigma_0\otimes\sigma_1+ c\sigma_1\otimes\sigma_1$ (combined with some coefficients $a,b,c$ to be determined case by case). $H_2$ induces mixing between the degenerated ground states. According to the idea of degenerate perturbation, the degeneracy will be lifted, and in the worst case, completely lifted.
Best Answer
The $A$ operators and the $B$s all commute with each other because they always share an even number of sites and therefore an even number of Pauli matrices. Therefore, these are all conserved quantities and can be replaced by their expectation value. The ground state is the state with eigenvalues $A = 1 = B$ in units where $\sigma$ is a Pauli matrix.
In terms of the spins the situation is slightly less trivial. Consider the configurations that satisfy the constraint $B = 1$, working in the z-basis. This requires that the spins have an even number of up spins and an even number of down (all up, all down, or two and two). However, if one tries to make a pair of up spins, one will find that on the neighboring stars (crosses) will need another spin flipped, and therefore the only possible configurations are ones where the down spins form closed loops in the background of up spins or (equivalently) vice-versa. Therefore the ground state has to be some superposition of these states with loops in them.
Now consider the constraint $A=1$. Writing $\sigma^x$ in the $z$ basis makes it clear that the operator flips the spin (this can also be understood as due to the anticommutation of $\sigma^z$ and $\sigma^x$). Therefore, $A$ flips the spins on a plaquette. As expected, this brings us to another state that obeys the $B=1$ constraint; the excitation can be seen as a small loop of up spins. Moreover, we can act with another $A$ nearby and make the loop bigger, and this way create loops of any size and shape by acting with the $A$ operators.
The ground state $|\psi_0\rangle$ of the toric code is the equal weight (magnitude and phase) superposition of all loop configurations of spin downs on the background of spin ups. One might call it a quantum loop gas. It is easy to see that this obeys the first constraint because each loop configuration itself has $B=1$. On the other hand, when one acts with $A_p$ each loop configuration gets changed into another one. However, it is easy to prove that this is the ground state since for a given $A_p$ this simply swaps two loop configurations that are the same everywhere except on plaquette p and have opposite spin configurations on p. These two configurations are both part of the sum, with equal weight, so that the state is left unchanged by this action. Therefore $A|\psi_0\rangle = |\psi_0\rangle$ and $A=1$.
Finally, note that one can even see that with open boundary conditions this state is unique. This is because the state must be made of loop configurations, and is therefore some superposition of them (by the $B=1$ constraint). But, the different loop configurations can be obtained from the state with no loops by acting with a product of $A$ operators creates the loops, one plaquette at a time. Therefore the different configurations must all have the same coefficient as the no loop config since the action of the product of $A$s cannot change the state (it also has eigenvalue 1 since each of its terms does) and it swaps those two configurations. On a cylinder (or torus), however, there are loops that cannot be created by products of the local $A$ operators - they are the loops around that wind the circular dimension. Therefore, there exists a ground state degeneracy in these cases corresponding to the number of configurations available to the unconstrained loops.