In which text first time "Gautama leaving Yashodhara for searching truth" story is written?

See also Which suttas in the Pali canon are relatively early or late? -- I'm not sure we know the sequence in which suttas were written -- so we can't say for sure which time is "the first time", though some people guess or assess via textual analysis that some bits might be later or altered somehow -- and/or maybe all suttas were written at the same time (i.e. at the 4th council).

If they were first time recorded in fourth council, then https://en.wikipedia.org/wiki/Fourth_Buddhist_council says it happenned in 1st century BC. And Gautama was in fourth century BC. So can we deduce that first time, it was recorded 200-300 years after him?

I think we're meant to understand that the suttas were remembered when they were first spoken (e.g. spoken by Gautama) ... and "recorded" in the First Council ("a gathering of senior monks of the Buddhist order convened just after Gautama Buddha's death in ca. 400 BC").

By "recorded", I mean that they agreed on what to memorise, what to consider as "canon".

They were later written in the Fourth Council:

The council was held in response to a year in which the harvests in Sri Lanka were particularly poor and many Buddhist monks subsequently died of starvation. Because the Pāli Canon was at that time oral literature maintained in several recensions by dhammabhāṇakas (dharma reciters), the surviving monks recognized the danger of not writing it down so that even if some of the monks whose duty it was to study and remember parts of the Canon for later generations died, the teachings would not be lost.

I don't know in which texts "Yashodhara" (or Yasodhara) is mentioned by name -- there are some References in her Wikipedia article.

One the sources (the main source?) of the detailed story of Gautama from before his "noble search" started (i.e. the story with details of his leaving his wife) is in the introduction to the Jataka tales (e.g. here) -- perhaps she isn't mentioned by name though, though his son (named "Rahula") is:

Within the chamber was burning a lamp fed with sweet-smelling oil, and the mother of Râhula lay sleeping on a couch strewn deep with jasmine and other flowers, her hand resting on the head of her son. When the Future Buddha reached the threshold, he paused, and gazed at the two from where he stood.

"If I were to raise my wife's hand from off the child's head, and take him up, she would awake, and thus prevent my departure. I will first become a Buddha, and then come back and see my son." So saying, he descended from the palace.

I'm not sure what the provenance is of the Jataka Tales. They're included in the Khuddaka Nikāya of the Sutta Pitaka but somehow not exactly suttas (I'm not sure whether or when the Buddhist councils were involved with them).

Gotama left his extended family, clan or royal lineage rather than merely Yashodhara. The earliest Pali suttas never mention Yashodhara but only Gotama's mother & father.

So, at a later time, while still young, a black-haired young man endowed with the blessings of youth in the first stage of life — and while my parents, unwilling, were crying with tears streaming down their faces — I shaved off my hair & beard, put on the ochre robe and went forth from the home life into homelessness.

Ariyapariyesana Sutta: The Noble Search

It seems Gotama has no interest in sex and women. The scriptures are not written like a modern romance novel or Hollywood movie.

Monks, I lived in refinement, utmost refinement, total refinement. My father even had lotus ponds made in our palace: one where red-lotuses bloomed, one where white lotuses bloomed, one where blue lotuses bloomed, all for my sake. I used no sandalwood that was not from Varanasi. My turban was from Varanasi, as were my tunic, my lower garments, & my outer cloak. A white sunshade was held over me day & night to protect me from cold, heat, dust, dirt, & dew.

I had three palaces: one for the cold season, one for the hot season, one for the rainy season. During the four months of the rainy season I was entertained in the rainy-season palace by minstrels without a single man among them, and I did not once come down from the palace. Whereas the servants, workers, & retainers in other people's homes are fed meals of lentil soup & broken rice, in my father's home the servants, workers, & retainers were fed wheat, rice, and meat.

Even though I was endowed with such fortune, such total refinement, the thought occurred to me: 'When an untaught, run-of-the-mill person, himself subject to aging... illness... death, not beyond aging, sees another who is aged, he is horrified, humiliated & disgusted, oblivious to himself that he too is subject to aging, not beyond aging. If I — who am subject to aging, not beyond aging — were to be horrified, humiliated & disgusted on seeing another person who is aged... ill... dead, that would not be fitting for me.' As I noticed this, the [typical] young person's intoxication with youth entirely dropped away.

Sukhamala Sutta: Refinement