If "ex nihilo nihil fit" means "out of nothing comes nothing" then how would one say "out of nothing comes something"? The best I can come up with is "ex quidem nihil fit." Is that translation correct?
I think quidem is wrong here, as it is an adverb. You can confirm this on the Lewis and Short dictionary. Also, you need to keep the ablative phrase "ex nihilo" (you changed it to "ex quidem").
I would use this phrase: aliquid ex nihilo fit. I'm using the word "aliquid" to mean "something", but there might be better choices.
With Pliny's well-known ex Africa semper aliquid novi in mind, is there any real need for a verb here?
I would use ex nihilo aliquid.
I would use the word nonnihil, "not nothing" or "something". It also makes the comparison to the original phrase clear.
Ex nihilo nonnihil fit.