Dipende tutto da come vuoi che avvengano le cose.
Se vuoi che il cookie si salvi alla sola selezione/deselezione del checkbox senza inviare dati al server, devi usare JS come fai adesso, ma lo devi fare nel modo giusto, leggi qui per tutte le spiegazioni su creazione/lettura/modifica/eliminazione, comprese funzioni già scritte per gestire il tutto.
Tieni presente però che in questo modo sovrascrivi il cookie ad ogni pressione dei checkbox.
Avendo un cookie che deve contenere più dati devi decidere un nome per il cookie, tipo "distretti", e come valore usare un array JSON contenente coppie chiave/valore "cb.value/cb.checked", poi quando generi i vari checkbox dovrai ciclare su questo array per impostarne lo stato.
Alla modifica del cookie dovrai ciclare su tutti i checkbox presenti sulla pagina per rigenerare l'array JSON.
Nell'array JSON potresti anche metterci solo i nomi dei checkbox selezionati invece di tutti col relativo stato, quelli non presenti li puoi considerare come non selezionati.
Se vuoi farlo in PHP hai 2 strade, semplice usando un form classico per inviare i dati al server ed elaborarli, più complicato, ma senza necessità di ricaricare la pagina, con chiamate asincrone AJAX ogni volta che clicchi su un checkbox.
I cookie in PHP si gestiscono così.
Anche in questo caso valgono le stesse cose del caso JS riguardo al contenuto del cookie.