Analyzing time complexity for change making algorithm (Brute force)
First, when computing the $n$-th fibonacci number $F(n)$, the number of branches (leaves) is not $2^n$, but exactly $F(n)$. But you can say it is $O(2^n)$.

As for the coin change problem it is not $O(n^C)$. $n^C$ is a polynomial, while the number of branches in the tree  grows exponentially. In other words, given $n$ number of coin denominations and constant $C$, each node has no more than $C$ children, and so the number of branches/leaves is at most $C\times C\times \dots C$ ($n$ times). In fact the actual number of branches is less than $C^n$, but is definitely bounded from above by $C^n$, and so is $O(C^n)$ (recall that big-O denotes the upper bound of a function).