At the beginning it's not possible to get more than 4 stars. When is it? Is it after a mission in the storyline or can something else unlock it?
You start with 4, as you noted. Unlock the next island and you can get up to 5. Unlock the third island and you can get 6 stars.. It has been a bit too long for me to remember what plot quests this event happens at however.