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.