Para agragar este tipo de vocabulario nuevo para Magento, debemos ir hasta el database de Magento buscar la base de datos de tu tienda ingresar a ella y encontrar las tablas llamadas "directory_country_region"

Ahora bien entramos en él y luego hacemos una exportación. Cuando tengamos la exportación abrimos el archivo y agregamos las regiones / estados o departamentos del país siguiendo la secuencia con la que el archivo que exportamos está. Ya teniendo todos nuevos regiones / estados o departamentos agregados en el archivo podemos guardarlo e importarlo.
485 CO Amazonas Amazonas
486 CO Antioquia Antioquia
487 CO Arauca Arauca
488 CO Atlántico Atlántico
489 CO Bolívar Bolívar
490 CO Boyacá Boyacá
491 CO Caldas Caldas
492 CO Caquetá Caquetá
493 CO Casanare Casanare
494 CO Cauca Cauca
495 CO Cesar Cesar
496 CO Chocó Chocó
497 CO Córdoba Córdoba
498 CO Cundinamarca Cundinamarca
499 CO Guainía Guainía
500 CO Guaviare Guaviare
501 CO Huila Huila
502 CO La Guajira La Guajira
503 CO Magdalena Magdalena
504 CO Meta Meta
505 CO Nariño Nariño
506 CO Norte de Santander Norte de Santander
507 CO Putumayo Putumayo
508 CO Quindío Quindío
509 CO Risaralda Risaralda
510 CO San Andrés San Andrés
511 CO Santander Santander
512 CO Sucre Sucre
513 CO Tolima Tolima
514 CO Valle del Cauca Valle del Cauca
515 CO Vaupés Vaupés
516 CO Vichada Vichada
También debemos hacer lo mismo con "directory_country_region_name" agragando la información del pais que no esté en el database de Magento, igualemte siguendo la secuencia con la que el archivo se abra.
NOTA: Para ver dicha configuración asegurate de actualizar el cache.