I have noticed Captains get promoted more frequently when you win a battle with a Heroic Victory.

Not sure if this is always the case, but thats how most of my promotions have occurred.