As in the title, I'm conflicted whether to use the former or the latter. Logically speaking, I'd rather choose "hearts" since we're talking about everyones', but some quotes found on the internet make me wonder.
Working off the assumption everyone only has one heart
As Nohat says here, everyone is a singlar word: Is "everyone" singular or plural?
To rationalise this, you are effectively saying 'every person' and thus you can see that the use of the singular is correct, fitting with 'has' as you've recognised and the singular 'heart'
So, like you can see that 'every person has a dream with stars in their heart' requires the singular heart so does yours.
Thus your sentence should read:
Everyone has a dream with stars in their heart