I imagine that there are potentially examples of this sort of behavior going back as far as 30-40,000 years or more, but there is is no direct (known) archaeological evidence left to make such cases. There are oral histories of indigenous peoples in Australia that indicate memories of things that do exist in the geological record to provide some evidence of this.
I’ll also point out that astronomical use is NOT equal to memory use. To make that claim you’d need a lot of additional evidence. In fact, I might suggest something stronger, particularly about Stonehenge. Stonehenge’s primary use was not an astronomical one. Its primary use was as a mnemonic device. The astronomical one was important for the ritual practice (we would call it spaced repetition in modern psychology and pedagogic contexts), but wholly tangential.
If you’re interested in the underlying evidence, Dr. Lynne Kelly has an excellent Ph.D. thesis on the topic, but you might find her book The Memory Code, which expands on the thesis, more accessible. She’s also got a great bibliography of these topics on her website.