Each of these sentences is technically correct:
In the sentence "He's had girlfriends that are too young", "young" is an adjective that modifies "girlfriends", and "too" is an adverb that modifies "young".
However, with the way that those sentences are constructed, "too" and "young", in this case, need to be taken together to function properly because they've become an adjective phrase, and the general rule for adjective phrases is that if they precede the noun they're modifying, they're hyphenated, and if they come after the noun they're modifying, they're not hyphenated. Otherwise, you have girlfriends. What kind? Young. What kind of young girlfriends? Too. And that's nonsensical.
That being said, they're not correct in the sense that, for saying that someone it "too ", you would never, ever say it this way.
As for when to hyphenate this type of phrase, and I apologize for the coarseness, but you could use the "blank-ass blank" test, which operates as such:
If someone were to come up to you and say the words:
I just bought a big ass car
lack of punctuation is intentional
... it would certainly not be correct to infer that they had purchased an "ass car" that is large, because, again, that's nonsensical. Instead, you would infer that they had purchased a large car, so the correct way to write this (admittedly colloquial) sentence is:
I just bought a big-ass car.