What is the most basic organism to respond to Classical conditioning (capable of learning)?
Very simple nervous systems are capable of learning  C. elegans, with only 302 neurons, is reportedly capable of both learning and memory.  There is a fairly large literature on the subject, as C. elegans is a popular research subject - a Google Scholar search gives about 40K hits, e.g. http://learnmem.cshlp.org/content/17/4/191.long

We have to remember that small is not necessarily primitive: the C. elegans nervous system (like every other one in existence today) has been optimized by millions of generations of evolution to do what C. elegans needs in order to survive.

Actual evidence of learning in nervous systems in the distant past is rare.  It's behavior, and behavior doesn't fossilize well :-)  Actual nervous systems apparently don't fossilize all that well, either.  The earliest well-preserved example I could find was this http://www.cam.ac.uk/research/news/520-million-year-old-fossilised-nervous-system-is-most-detailed-example-yet-found from 520 million years ago.  But since learning would give a creature a survival advantage, I'd guess that it evolved fairly early.