Marque Identificar cidade automaticamente em WooCommerce → Configurações → Entrega → Configurações de entrega, seção Otimização da calculadora.
Sem ela, o plugin descobre só o estado (pela faixa do CEP) e manda a cidade vazia pro cálculo. Com ela, consulta a cidade no ViaCEP a cada cálculo, o que leva menos de um segundo.
Se o ViaCEP estiver fora do ar, a cidade volta vazia naquele cálculo.