While the words for "with" in most Romance languages seem to be direct descendents from Latin "cum" (e.g. Spanish/Italian "con", Portuguese "com", Romanian "cu") it got replaced by "avec" in French. Could it be that this is due to the fact that the latin obscenity for the female genitalia "cunnus" (whose reflexes seem to survive as taboo word in most Romance languages) also came to be pronounced "con", so that people tried to avoid the putative preposition "con" due to its obscene homophone?
(It's probably hard to tell with certainty why this particular change took place, but I'd also be happy to know whether avoidance of words with taboo homophones is a well-known linguistic phenomenon and attested or at least conjectured in other cases.)