The origin of this expression is unclear. Wiktionary says about it:
Die Wendung ist seit dem 20. Jahrhundert bezeugt. Die Herkunft des Wortes »paletti« ist unsicher. Weder Erklärungen aus dem Italienischen noch aus dem Hebräischen können einen plausiblen Weg ins Deutsche namhaft machen.
The entry lists three sources ("Etymologisches Wörterbuch der deutschen Sprache" and Duden, twice) that I couldn't check.
The oldest reference I've found is in an article of "DER SPIEGEL" from 1972, and it's a quote that, according to the context, is from 1970:
"Nimm den Strafantrag (wegen Körperverletzung) zurück, und alles ist paletti."
