But how is the execution also dependent on the message (the inputs)?
Actually, there are (at least) two potential timing attacks.
One is as you suggest; the timing (at least, for this simple exponentiation algorithm) is related to the hamming weight of the secret exponents. However, as you have observed, the secret exponents aren't dependent on the ciphertext.
However, there is a second potential timing variation that the attacker might attempt to exploit. Suppose that you compute an intermediate value $C^{k} \bmod N$, and that value just happens to be unusually small. Then, depending on the bignum library you use, it is possible that the next operation (especially if it is square, possibly if it is a multiply) will go unexpectedly fast, and that timing variation would tell you if $k$ was an intermediate exponent (which gives you a number of bits of the secret exponent).
Now, in practice, it doesn't work that well; it's hard to compute $C$ values where $C^k \bmod N$ is small (and it becomes even harder if the implementation uses CRT, there you'd need values where $C^k \bmod p, q$ are small.
So, what you end up doing is passing in random $C$ values, looking for values that are processed unexpectedly fast, and deducing things from that.
The proposed solution of Kocher is "blinding" by a adding a random value to the message.
I'm pretty sure you misunderstood. For one, adding a random value to the message gives an unrelated result.
If Paul proposed anything (he has proposed a number of things; I don't remember hearing these specifically from him), he may have suggested one of the following two things:
Multiplying a random value to the message. That is, select a random value $r$, compute $r^e \bmod n$ and $r^{-1} \bmod n$; then multiple $c' = (r^e \bmod n) \cdot c$; perform the RSA operation on $c'$ resulting in $t' = RSA_{private}(c')$, and then compute the final $t = t' \cdot (r^{-1} \bmod n)$. The RSA operation is done on an equidistributed value, and hence there aren't any message-based side channel leaks there
Add a random value to the exponent. That is, (and I'll assume you're doing CRT here) select a random value $r$, and compute $t_p = (c \bmod p)^{d_p + r(p-1)} \bmod p$ (and similarly for $q$). Except for a couple of the lower order bits, the exponent you use are randomized (and that could be covered by always selecting $p \equiv q \equiv 3 \pmod 4$)
On the other hand, Paul would never suggest either of the above as the sole protection for a badly leaking modular exponentiation routine. Using power analysis (invented by Paul), you could obtain the exponent from a single trace; this would foil either of these countermeasures.
