I haven't investigated this question in any detail, but a natural thought is that the emergence of sentience coincided with (either as a byproduct of or causal factor in) the Cambrian Explosion, ~540 million years ago. The capacity for valenced experience probably arose either simultaneously with the capacity for general awareness or shortly thereafter. With the capacity for valenced experience comes the capacity for negative hedonic states, which under many circumstances would constitute suffering, in my view. Depending on how robustly you're defining 'desire,' desires might also have arisen around the same time (e.g., many animals probably have the basic desire to avoid negative hedonic states).

See Michael Trestman's 2013 paper "The Cambrian Explosion and the Origins of Embodied Cognition" for more on the connection between consciousness and the Cambrian explosion. Max Carpendale also wrote about this topic on the Forum last year. For the view that consciousness emerged much later (i.e., not until mammals), see Stanislas Dehaene's 2014 book Consciousness and the Brain: Deciphering How the Brain Codes Our Thoughts. For general discussion of the evolutionary origins of consciousness, see Peter Godfrey-Smith's excellent 2017 book Other Minds: The Octopus, the Sea, and the Deep Origins of Consciousness.