Desde tu función, tendrías crear los `option` que resultasen de la lectura de las ciudades almacenadas y asignarlos al `select`, alcazándolo por su `id`.

Imaginemos que almacenas las ciudades como objetos, con dos propiedades, `id` y `name`, puedes poner algo así en tu función:

[<kbd>**`VER DEMO`**</kbd>][1]

    let allCities = JSON.parse(localStorage.getItem("cities"));
    if (allCities !== null) {
      const fragment = new DocumentFragment();
      const selCity = document.getElementById('city');
      for (const city of allCities) {
        const option = document.createElement('option');
        option.value = city.id;
        option.textContent = city.name;
        fragment.append(option);
      }
      selCity.append(fragment);
    }

Imaginemos que tus ciudades son un elemento simple, la función podría quedar así:

[<kbd>**`VER DEMO`**</kbd>][2]

    let allCities = JSON.parse(localStorage.getItem("CITIES"));
    
    if (allCities !== null) {
      const fragment = new DocumentFragment();
      const selCity = document.getElementById('city');
      for (const city of allCities) {
        const option = document.createElement('option');
        option.value = city;
        option.textContent = city;
        fragment.append(option);
      }
      selCity.append(fragment);
    }

### PD

Nótese que hemos usado un fragmento, para hacer append de cada `option` y sólo al final del bucle hacemos append de ese fragmento en el `select`. Esta es la práctica recomendada cuando modificamos elementos en bucle, porque si haces append directamente en cada iteracción, el DOM se renderizará en cada append. Hemos usado también `createElement` porque es el modo más seguro de crear elementos dinámicos, evitando posibles ataques XSS.

  [1]: https://jsfiddle.net/acedano/oLsh48zd/17/
  [2]: https://jsfiddle.net/acedano/e2jwdpsa/11/