Bom dia,
Sim, essa transportadora de SP pode fazer frete em GO ou qualquer outra UF (emite CTE com CFOP 6932). Não há necessidade de abrir uma filial em GO (desde que seja avaliado outras questões como custos e a parte operacional, por exemplo).
Dito isto, lembro que essa operação interna em GO que o icms é isento (CST 040) conforme inciso LXI do Art. 6 do anexo IX do RCTE/GO desde que seja destinada à contribuinte do ICMS estabelecido naquele estado. Ou seja, se o frete for CIF ou FOB e o pagador do frete ser contribuinte do ICMS, o ICMS do frete será isento.
Como uma dica: Transporte de cargas pode dar muito problema fiscal se for feito sem planejamento. Especialmente se a transportadora de SP (no seu caso) for trabalhar em MS e MT onde tem muita fiscalização nas divisas. Por isso, ANTES de colocar caminhão pra puxar carga saindo de outro estado, o ideal é pesquisar de forma antecipada.