Oh no, I don't think you understand how big the problem space actually is.
https://en.wikipedia.org/wiki/Kruskal%27s_tree_theorem
A very simple set of 3 possible combinations blows up into a possibility that is 2 to the 2 teterations 1000. This number cannot be explained to the human mind realistically.
> What pre-existing ideas were combined to bring it into existence from non-existence?
This depends what you believe about existence. For example if you believe in mathematical existences then 'simple' exploration of the problem space can lead you to find anything that could possibly exist in the conditions our physical universe allows algorithmically. And the number of those things are for a practical matter, infinite.
>we are a creative species. We can create new things. Somehow.
You are viewing this from a very human perspective scale though. Your individual cells are massively creative containing solutions to a staggeringly huge number of problems, including ones they've not seen before (take the immune system for example), yet how 'intelligent or creative' would you consider your cells to be.
Simply put you're ignoring algorithmic creativity and problem space exploration as it is, until you at least look at how simple systems create infinite complexity already.