For a long period of time to be someone's companion was very dubious. In particular a man's female companion and a woman's male companion were euphemisms for lover. In Webster 1913's Milton example, the companions were sent to hell (viz fallen) as companions; i.e. they engaged in illicit activities (probably sex) together.

Traveling companions, however, were people who sought each other's company to aid safe passage through unknown territory.