700-660 million years ago
In this fictional treatment of the history of life on earth, I am going to err on the side of caution and suggest that the oldest worms date to about 620 million years ago (rather than the studies which have suggested ages of 1.1-1.2 billion years for the first worms). Since cnidarians and sponges are more primitive than worms, I will postulate that these animals evolved prior to that, starting around 700 million years ago.
Fossil strata which have been dated at more than 1.2 billion years old
contain animals--not only contain fossils of radial-soft bodied organisms,
they contain burrows which seem to have been made by mucus-producing worms
(simulated in the images above; Rasmussen, 2002). There is a site in India
whose worm burrows have been dated at 1.1 billion years ago, although
some dispute this date. Recently, another site with apparent signs of
primitive animals (jellyfish relatives) and worm burrows has been dated
at 1.2 billion years old at the youngest (Seilacher, 1998; Kerr, 1998b;
Morris, 1993). Other Ediacaran fossils are known by 610-600 million years
ago and more diverse assemblages of organisms are known by 555.3 million
years ago (McMenamin, 1996, Minnerop, 2000). They were largely replaced
by the animals of the "Cambrian explosion" which began about
545 million years ago.