From Dune (1965 printing) -- page 307 -- the whole naming thing didn't make it exactly into the movie the way it is in the book
So my take after all of this is that this both represented his learning how his prescience worked, and that he could make decisions that were not in his future-memory.
'Now what name of manhood do you choose for us to call you
openly?' Stilgar asked.
Paul glanced at his mother, back to Stilgar.
Bits and pieces of this moment registered on his prescient memory, but he felt the differences as though they were physical, a presence forcing him through the narrow door to the present.
'How do you call among you that little mouse, the mouse that jumps?' Paul asked remembering the pop-hop motion at Tuono basin. He illustrated with one hand.
A chuckle sounded through the troop.
'We call that one muad'dib," said Stilgar.
Jessica gasped. It was the name Paul had told her, saying that the Fremen would accept them and call him thus. She felt a sudden fear of her son and for him. Paul swallowed.
He felt that the played a part already played over countless times in his mind
'I am Atreides,' Paul whispered, and then louder: 'It is not right that I give up entirely the name my father gave me. Could I be known among you as Paul-Muad'Dib?'
And Paul thought: That was in no vision of mine. I did a different thing.
'I will tell you a thing about your new name,' Stilgar said. 'The choice pleases us. Muad'Dib is wise in the ways of the desert...Muad'Dib we call instructor of boys. That is a powerful base on which to build your life.
The muad-dib/gerbil had important mythical qualities, but the Fremen had not yet connected their messiah to the name muad-dib yet.
It was "natural" in that he foresaw the choice of his name and ended up being called "Muad'Dib" despite that he actually didn't choose that name exactly as his foresight showed him.