Uma transportadora de Minas Gerais iniciando o serviço de transporte no Pará com destino ao Estado do Pernambuco. Deverá pagar o ICMS a favor do Estado onde iniciou o serviço (art. 11, II, 'a', Lei Kandir), no caso, o Estado do Pará.
O MANUAL DE ORIENTAÇÃO DO CONTRIBUINTE - MOC, PAG. 133 determina que o emitente do CT-e destaque o ICMS, mas esse destaque apenas administrativo, não é fiscal, pois pertence ao Estado de início da prestação do serviço (e seu CT-e é Minas Gerais).
Mas essa regra não vale pra você por ser optante do simples, não destaca ICMS nos documentos fiscais, conforme ensina o art. 57, §2º, I, Resolução 94/2011.
Também, bom lembrar o que diz o artigo 59, VI, mesma Resolução 94/2011:
"Art. 59. A ME ou EPP optante pelo Simples Nacional não poderá consignar no documento fiscal a expressão mencionada no caput do art. 58, ou caso já consignada, deverá inutilizá-la, quando:
...
VI - tratar-se de prestação de serviço de comunicação, de transporte interestadual ou de transporte intermunicipal".
ATENTO: o que o art. 59, VI, acima estar dizendo é que quem contratar optante do simples para prestar serviço de transporte não faz jus a crédito fiscal!