Both answers are instructive and helpful. I will use Gianluca's code as it is attractively simple and applies to more situations. The advice from both contributors about how to use rules helped my understanding. FixedPoint seems excellent for keeping code simple.

Update: Ha! Gianluca is absolutely correct about Expand[c] being evaluated immediately since you used a plain Rule instead of RuleDelayed. I had noted that, but then went on to explain why none of your other rules would ever evaluate. In doing so, I had chosen to change your Rules to RuleDelayeds to clearly illustrate the problem. Then, obviously, I answered the question as if it had originally used RuleDelayeds. I'm only pointing this out to make it clear that the real reason your original code failed is that you weren't taking into account how rules are used in ReplaceRepeated and related functions. I.e. just changing c_ -> Expand[c] to c_ :> Expand[c] doesn't fix the problem. And of course, Gianluca's suggestion avoids that entirely by not using any sort of replacement function.

One problem is that your rules contain this:

c_ :> Expand[c]

The pattern c_ will match anything. Also, these functions stop performing replacements to a subexpression once a rule has been matched. So, even though you're using ReplaceRepeated, every single time it matches the whole expression and so the only rule you're ever applying is the Expand one.

I'm guessing that you want something like this:

myrules = {n_ Cos[a_] Cos[b_] :> n (Cos[a + b] + Cos[a - b])/2, n_ Cos[a_]^2 :> n (1 + Cos[2*a])/2};
k[0, t_] = 1;
k[n_, t_] := FixedPoint[Expand@*ReplaceRepeated[myrules], Cos[t]*k[n - 1, t] + Cos[n*t]];