What was the first time clothing moved beyond necessity and a widespread trend of clothing emerged?
There are Cro-Magnon remains in Europe (ca. 35000 years BP) that are buried with red ocher which very likely were transferred from dyed veils used to protect the dead from the evil eye (later, with Christianity, red went out of fashion and blue was in, after which white came to replace blue in both weddings and shrouds).
Culturally distinctive pottery decoration styles pre-date the invention of agriculture (they appear ca. 16,000 years BP in China and Japan many thousands of years before agriculture is invented unlike in the Fertile Crescent where agriculture was developed before pottery). And, there is every reason to believe that distinctive pottery ornamentation was accompanied by similarly distinctive clothing ornamentation, but that the clothing just didn't preserve well.
I read a journal article once that hypothesized that two regional groups within the first farmer Neolithic Linear Pottery Culture (LBK) probably had two distinct cultures because they used different beading styles. This would be ca. 6,000 BCE (i.e. 8,000 years ago).
Ava of the highlands who was buried in Scotland ca. 2500 BCE (about 4500 years BP), was buried with a manicure tool. Decorated clothing is found on mummies preserved in peat bogs and in the desert environment of the Tarim basin, in the later case dating to ca. 2000 BCE (about 4000 years BP).
Similarly, amber jewelry was common place in the hunter-gatherers of Northern Europe (e.g. Scandinavia and the Baltic States) and was so popular that it was exported as early as the Bronze Age (ca. 2500 BCE and onward) to destinations as distant as Egypt, from which decorative items were brought back in trade that can be identified with particular craft shops in Egypt.
While fashion is probably considerably older than these examples, prior to the invention of either pottery or agriculture, there may have been much less material excess, so fashion was probably dictated by which materials were available from year to year, rather than more creative and self-expressive motives.
For fashion trends that were remembered as trends, here's one of my favorite quotes of all time:
“Because King Ling of the State of Chu loved a slender beauty with a narrow waist, many people at court starved to death.” (Zhanguo ce, circa 200 BC, describing the situation of 530 BC)