I assume you meant to write whether instead of when.

So this is pure speculation, I would guess this kind of behavior will date back to the last common ancestor. Great apes and humans split somewhere between 5 and 23 million years ago. We haven't actually found any fossils of this animal, hence the big time range. Anyway at the time of the split, neither humans or great apes existed. We have evolved alongside each other to what we are today. This makes me feel that use of medicinal plants is a learned behavior dating back millions of years.

As to the exact mechanism to learn this I would speculate that it comes for eating plants. It is very likely that the LCA was an omnivore. Say animal eats plant, weirdly animal feals better. After enough time of doing this animal connects the dots and knows a specific plant feels better. After enough generations and resulting increases in intelligence, it is not a big leap to seeing if rubbing a plant on your body makes you feel better.

This could of course come after the LCA. Convergent evolution exists so it seems safe to say convergent learning does too. Until there is evidence to the contrary. Learned behavior from the LCA seems more likely to me.