Temos, antes de mais, de nos centrar nas características dos verbos, o que, convenhamos, nem sempre é fácil, dada a tendência de muitos dicionários para considerarem intransitivos verbos como vir, quando este verbo carece quase sempre, para completar o seu sentido, de um complemento. Nos dicionários em que essa informação surge, estes verbos surgem como transitivos indirectos, incluindo-se nesta designação todos os verbos que completem o seu sentido com um complemento introduzido por uma preposição.

Importa, ainda, dizer que a inovação do Dicionário Terminológico neste aspecto é diminuta, uma vez que o complemento destes verbos é, já, considerado obrigatório na Nova Gramática do Português Contemporâneo, de Cunha e Cintra, p. 144.

Voltando à caracterização dos verbos em apreço, vir e chegar, no dicionário da Academia das Ciências de Lisboa não é explicitada a tipologia destes verbos (transitivo, intransitivo…), mas são dadas acepções em que surgem construídos com as preposições que regem em alguns contextos. Assim, vir surge associado às preposições a e para («vir a/para Lisboa»), designando o ponto de chegada, e de, indicando o ponto de partida («vir de Lisboa»). As preposições a e de podem ainda designar o meio («vir de moto», «vir a cavalo»). Também ao verbo chegar se associam as preposições a e de, com o mesmo valor, respectivamente, ponto de chegada e ponto de partida.

O Dicionário Houaiss apresenta a tipologia dos verbos:

Vir — Transitivo indire{#c|}to («vir de Lisboa»), intransitivo (ex. «olhou e lá vinha o marido») e transitivo pronominal («veio-se embora»);
Chegar — Transitivo indire{#c|}to («chegar à janela») e intransitivo («a noite chegou»).

O Grande Dicionário da Língua Portuguesa, da Porto Editora, indica:

Vir — Intransitivo.
Chegar — Intransitivo, transitivo e reflexo.

Não apresenta exemplos ilustrativos. Alerto para o facto de, na maioria das situações, o verbo vir ser transitivo indirecto («vir de/a algum lado»), situação que, na classificação deste dicionário, não é tida em consideração.

Consultei ainda o Dicionário Prático de Regência Verbal, de Celso Luft, Editora Ática, que considera ambos os verbos quer intransitivos quer transitivos indirectos.

Perante o exposto, é possível concluir que, em determinados contextos, tanto chegar como vir se constroem com um complemento oblíquo.

Daí que «de Paris» deva ser considerado complemento oblíquo em ambas as frases. Recordo ainda um teste referido por Inês Duarte, no Capítulo 10 da Gramática de Língua Portuguesa, de Mira Mateus e outras, Editora Caminho, 5.ª edição. Refere a autora que podemos distinguir complementos de adjuntos (entenda-se modificadores) através do seguinte teste: os complementos não permitem que seja feita a pergunta a) «o que fez + sujeito + grupo preposicional/adverbial?» ou b) «o que aconteceu a + sujeito + grupo preposicional/adverbial?», obtendo como resposta o predicado (verbo e seus complementos).

a) «o que fez + sujeito + grupo preposicional/adverbial?»
      *O que fiz de Paris?
      ?Cheguei.

Repare-se na boa construção da pergunta perante um modificador:

      O que fiz na semana passada/ontem?
      Cheguei de Paris.