olá,
há alguns cenários que imagino para este caso:
1. você está usando o mesmo navegador que gerencia o WordPress para fazer testes. então quando você desloga do WP e vai testar um produto no carrinho, já aparece o CEP de São Paulo. isso pode ser devido os cookies no seu navegador. o ideal seria ter um navegador apenas para testes ou, ao menos, fazer os teste em uma janela privativa.
2. em WooCommerce > Configurações > Geral, você configurou em Localização padrão do cliente a opção Endereço base da loja. Só que se sua loja for em São Paulo, o sistema adotará que qualquer usuário na loja é de São Paulo… até que o usuário se cadastre e diga sua real localização.
o indicado é que use a opção Nenhuma localização por padrão. com isso, o carrinho do WooCommerce não mostrará o frete até o usuário preencher o campo CEP.
3. se não se trata de 1 ou 2, só resta que isso tem a ver com algum plugin ou código que adicionou. e neste plugin ou código há alguma configuração que adota que usuários não-logados são de São Paulo e, por isso, ao acessarem o carrinho vêem o frete grátis. precisa verificar seus plugins ou códigos customizados e corrigir onde isso pode ter sido configurado.
boa sorte e sucesso.