Is this a saltwater millipede?
This is indeed a polychaete worm, and likely a member of the beachworm family Onuphidae. 

From the Marine Education Society of Australasia  :


  Polychaetes are particularly common on and in muddy and sandy shores. Their most obvious feature are the pairs of parapodia appendages. One pair comes from each body segment. These parapodia are used for crawling and swimming. "Para" means "like", and "podia", "pod" or "ped" means "legs". These parapodia are often tipped with hardened spine-like setae or dorsal cirri. 


You can find some good informaiton on beach worms here, and information on the distribution, abundance and
population dynamics of various species here.

I'm sure a quick message to Dr. Pat Hutchings, the Austrtalian Museum's polychate expert, would prove to be be your best chance to get a species identification. 

For those interested in additional polychaete identification, you can download a digital ID key.