They came from retroviruses. The restriction endonucleases are part of the insertion mechanism employed by retroviruses. They need to open up double stranded DNA in the host to insert their genome sequence. The genome sequence they inserts encodes the enzymes that cut open the DNA.