The believe the first mention of the Golden Path was is in Dune Messiah, but did Herbert ever mentioned when Paul first became aware of of the Golden Path?
Did he foresee it shortly after undergoing the spice agony or not until then events of Dune Messiah?
Or is it yet another thing Herbert left ambiguous?
Long answer ahead: Short answer; when he took the Water of Life, but he doesn't CALL it that until Dune Messiah.
Tricky question; the Golden Path was more a concept, than a technical path -- he had a desired goal, and at decision points, there was a direction that would go towards it -- that was the path. Although it constrained his actions considerably, it wasn't quite as much of a straight jacket as it appeared, as many variations developed in it, and it still came to fruition. (For example, he didn't see having twins, nor did he see Leto taking over, but this didn't prevent the path. Think of it as a real path; it's an area of travel with a destination, not just a set of footprints that must be exactly walked in. Think of the main path as the Optimal Path, but not the only one.)
Paul first became aware of it, in a sense, when he first drank the Water of Life in Dune; but at that point he only saw a limited portion of it, that being what was needed to get past the Crux of the Guild and Empires coming to Arrakis.
"They have a narrow vision of time," Paul said. “They can see ahead to a blank wall marking the consequences of disobedience. Every Guild navigator on every ship over us can look ahead to that same wall. They'll obey."
At this point, there is a possible end to prescient paths, the destruction of the Spice that allows prescience. So, at this point, the Golden Path exists, but like all other prescient seen paths, has to go thru this 'choke point' first.
The eventual goal of the Golden Path was the survival of Mankind as man; other options included the perpetual enslavement or destruction of Man, either by the return of the Machines, or via the working of Prescience; strong enough prescience would allow the user to route man into a controlled path, and that 'leads ever down into stagnation.'
The Golden Path produced two main effects; a strain of humanity that was invisible to the prescient eye, and the scattering. In effect, many humans were now invisible to forseeing, and scattered across the universe, it would be nearly impossible for humanity to actually be killed off, as no one could know where all humans were, due the the first effect. In effect, their 'seed had been scattered to the stars.'
But, there's nothing that says Paul saw the entire path at any point; he talks about the future as a path over hills, that is not always fully visible, and, when he surrenders to Leto in Children of Dune, recognizes that Leto has seen more than he has.
Paul heard the truth in Leto's words, spoke in a low voice which acknowledged the greater breadth of his son's vision. "I did not see that among the choices."
So, his vision of it seems to have been for mankind to be free of the shackles of predestination, and therefore free for the unconscionable manipulation that he, himself, was able to engage in. But, what he could not see, was that this goal was also needed for mankind to survive at all:
Paul said. "I know this. Every man should have such an auditor. I will only ask this one thing: is the Typhoon Struggle necessary?" [Leto] "It's that or humans will be extinguished."
So, now that you've waded through my long-winded answer.. What it comes down to, is that he saw PART of it even as a child; his vision of his travel to Arrakis was where the path started, although he did not know it, and didn't see it as such. But his first true 'Vision' where he attempted thereafter to follow it was when he took the Water of Life, even though this was an incomplete vision that he later expanded upon.
You might also find this of use: Dune Wiki on the Golden Path
