At 5, one of my kids loved to flirt with the girls. My other son played with a girl who was a tomboy because they liked rough and tumble and both gave as good as they got.

There are so many ways that young kids can identify strong characteristics, even at 5 years old. I can't guarantee they won't change (although my kids haven't changed as far as I can recall).

The first incident I remember (while not gender related) was my son when he was 6 months old. He HATED scratchy fabric from the scarf from a bear. We had to cut the scarf and the tag off this bear. Over a decade later, he still has that same fussiness with fabrics. This tells me that some preferences are there from a very young age.

I could very well imagine some kids feeling at odds with their birth gender from a very young age.