originate + from / with / in / as

At and on as well.

• as has two relevant connotations. The first is characterization of one thing by another (I used the screwdriver as a lever), and here it's used for things that start as one thing (i.e, at origination) and become another:

  Anomalous cosmic rays (ACRs) that originate as interstellar neutral atoms traveling into the heliosphere....

  That is the ACRs started out neutral but became ionized in the solar wind. The second connotation is synchrony (I came in as he was leaving). Thus:

  Rock crystals, believed to originate as water slowly frozen into permanent ice....

  Here the rock crystals didn't start out as water; they came about when water froze.

• at is used with points in time and space. For the former,

  Why did not the longitudinal system originate at the same time as the transverse system?
  
  The latter makes for a particularly popular usage in anatomy and systems of transportation and communication. From Gray's Clinical Neuroanatomy:

  ... a group of cells that originate at the edge of the neural plate but remain in the surface....

  and from a book about the Penn Central Railroad:

  Nine combinations of preblocked trains are programmed by the Penn Central for the East St. Louis gateway, seven of which originate at Big Four Yard and two at Conway Yard.

• from, in Both these prepositions tell us the origination of what originates, and they can often be used interchangeably. Consider

  The liturgy originated in early Church rites.
  The liturgy originated from early Church rites.

  For things that have clear interiors behind boundaries, in is preferred:

  The idiom originated in Germany.

  Otherwise from would be more apt:

  The English language originated from German.

  For factual happenstance, use in; for implications of causation, use from. Thus

  The Missouri River originates in Montana.

  but

  The Missouri River originates from Bower's Spring.

• on Originate licenses the preposition on, when the point of origin is on top of something or on the surface of something. This is again popular in anatomy -- Both muscles originate on the lateral portion of the ilium; The psoas major and iliacus muscles originate on the posterior abdominal wall.... . Also [Block slides] commonly originate on steep slopes.... and Did life originate on Mars?

• with The meanings of with all have some sense of accompaniment. This allows the connotations of close association (a shirt with stripes) and responsibility (Leave it with me). The latter is reserved for persons, literal --

  The movement may originate with women, who, with larger education, have developed great ability in associated effort.

  or figurative --

  Bills of all kinds except money bills may originate with either house.

  But this does not eliminate a usage of pure concommitancy:

  The extremely important and varied group of monoterpenoid Índole alkaloids originate with the condensation of tryptophan with secologanin to give Strictosidine,....

  In other words, when you're doing organic chemistry some alkaloid compounds arise alongside the condensation of other compounds.

Overall your intuition matches what's in the books, i.e. the google corpus. Unfortunately that is often the only way with prepositions to see what they usually collocate with. Well, here we go, let the ngram bombardment begin. Firstly, you rightly picked four out of the top five prepositions used after originate.

I'll spare us the analysis of what comes after the prepositions, it's the usual determiners, a, the, this, any, etc. Due to the limitations of length in ngrams I had a look at the nouns following our prepositions.

From and in

So our top two prepositions match your gut feeling pretty much. From is stronger with physical stuff than in, which actually has two countries and what is likely the start of a few noun phrases (experience, connection, ignorance and causes). Notably God is in both very high and also a toss-up, even including the next preposition.

With

This is a bit more tangible, the top ten collocations for with are all people or organizations - and of course God.

At

This one of the top five is not in the question, and it's without many surprises. It goes with places and times.

As

Here we get a bit sciency, the first two are again start of some noun phrases, then the by which google categorizes as noun for reasons unknown followed by a bunch of biology and every science that uses waves.

Remark

One thing I want to reiterate, these are the top ten nouns that follow those prepositions in the books google digitized. That does not make any statement about what comes after number ten. That said, for countries in outshines from by one order of magnitude. Thus, for countries in is the better option. When I showed the top collocations for with above it showed people and organizations. However, in is still more popular with Congress. The same is mostly applicable for the rest of the with collocations. The notable exceptions are Moses and Sir. Therefore, for specific people with seems the way to go, although that does not apply to Jesus and God.