Finding a complexity by solving inequality
You can’t use $O(m) + O(m) = O(m)$ in an inductive proof, since the hidden constant will keep blowing up. To see this more closely, suppose that you bound $C_{n,m}$ with $A\cdot m$. Then
$$
C_{n,m} \leq C_{n,m-1} + C_{n-1,m-1} + O(1) \leq 2A(m-1) + O(1).
$$
The right-hand side will generally not be at most $Am$.

Instead, let's try to use Pascal's identity, $\binom{a}{b} = \binom{a-1}{b} + \binom{a-1}{b-1}$. We guess that $C_{n,m} \leq A\binom{m}{n}-B$. Then
$$
C_{n,m} \leq C_{n,m-1} + C_{n-1,m-1} + O(1) \leq \\
A\left(\binom{m-1}{n} + \binom{m-1}{n-1}\right) - 2B + O(1) =
A \binom{m}{n} - 2B + O(1).
$$
For $B$ larger than the hidden constant in $O(1)$, the right-hand side will be at most $A\binom{m}{n} - B$, and so we will be able to prove the induction hypothesis. For given $B$, we can choose large enough $A$ so that $C_{0,k} \leq A \binom{k}{0} - B$ would hold. However, we reach a problem when considering the other base case $C_{k,0} \leq A \binom{0}{k} - B$. Therefore we need to fix our strategy.

At this point, we leave it to the reader to find the right binomial coefficient to add.