Esclarecemos que na contratação de um tomador de serviço de transporte estabelecido em  Minas Gerais por um prestador de serviço de transporte estabelecido em São Paulo, a premissa é a mesma de todos os Entes Federativos quanto a utilização da CFOP.

A Lei Complementar n°87/96 (Lei Kandir) em seu artigo nº 12 determina o seguinte:

Art. 12. Considera-se ocorrido o fato gerador do imposto no momento:        

I - da saída de mercadoria de estabelecimento de contribuinte, ainda que para outro estabelecimento do mesmo titular;

Portanto, é considerado como fato gerador do imposto do ICMS, o início da prestação de serviço de transporte interestadual ou intermunicipal.

Já o artigo n°11 da Lei, determina como local da operação ou prestação para a cobrança do imposto onde tenha iniciado a prestação: 

Art. 11. O local da operação ou da prestação, para os efeitos da cobrança do imposto e definição do estabelecimento responsável, é:
 II - tratando-se de prestação de serviço de transporte:
         a) onde tenha início a prestação;

Concluímos que o início e o fim da prestação do serviço contratado se deu dentro do Estado de São Paulo, a emissão do documento deve seguir as diretrizes da Nota Técnica 2013_014 item 2:

"Se UF de início da prestação = UF de fim de prestação (e UF fim <> EX) CFOP deve iniciar por 5".

Sendo assim, a escrituração no livro fiscal do tomador estabelecido em Minas Gerais será o CFOP 2352, visto que as UF's se diferem entre Prestador e Tomador.