A palavra companheiro – já aqui abordada – tem de facto que ver com com o latim, com o significado referido na pergunta, mas não de forma direta. Ter-se-á formado com base em companha, palavra que terá sido motivada por outra muito semelhante que se usava no latim da Gália e que decalcava uma expressão germânica. Uma explicação alternativa é considerá-la uma adaptação antiga do castelhano compañero, cuja base de derivação, compaña*, se ligaria à referida palavra vinda de França**. Convém atentar no que se diz no Dicionário Houaiss: «[do] latim vulgar *compania, formado de cum `com´ + panis `pão´, paralelo ao latim gaulês companìo, por sua vez, decalque do germânico gótico gahlaiba, de ga `com´ + hlaiba `pão´; segundo [Antenor] Nascentes, o signficado do latim vulgar *compania `conjunto de pessoas que comem seu pão juntamente´ ter-se-ia generalizado para `pessoas que vão juntas´ e, depois, se especializado, como termo militar e para fazer referência à `tripulação de uma embarcação´; [...]; formas históricas sXIV cõpanha, sXIV conpaña, sXV cõpãha.»

Sobre

* Companhia é uma variante de companha e também se atesta na Idade Média. Hoje é a palavra mais empregada nos sentidos de «presença de outra pessoa» e «empresa».

** O português companheiro é, portanto, cognato do francês compagnon, com o mesmo significado. Sobre a forma francesa, ler Antoine Thomas, "L'Étymologie du mot français compagnon" (agradeço ao consultor Gonçalo Neves a indicação desta referência).