As Cardinal Ape says, some examination is needed.
What happens is that only a general not in a stack will show the promotion feature. So what I do is I click on the message which takes me to the region where the general is. Then I search for the general. Occasionally this is a bit confusing as the names do not seem to directly match.
Then when I find the general, often buy taking him out of the army/corps in which he has been and I see the promotion light up, I put his troops under command of a different general if I have a spare and click on the promote button.
You are correct about the effect of a promotion. One star becomes two.
Where you do this is in the tent like icon.