There are multiple approaches to emergence, and I consider this to be the most valid, also agrees with my personal research regarding systems and interaction: emergence is just a subjective appreciation granted by reason.
To start, systems (the formal approach to things and objects) are just mental concepts. A constellation does not exist, the sky has only stars (and as you state, stars doesn't exist, matter is just a bunch of atoms). A rainbow does not exist, it's all molecules, photons, etc. It is you that create the rainbow in your mind. Same happens with a rock pebble, except that at different scales. An economic system is just a mental idea, etc. We can say that any object is defined by a subject. Paraphrasing Berkeley, systems can't exist outside a mind.
In consequence, systemic features ---such as emergence--- are also mental concepts. If you consider your subjective perception regarding the concept of atom (what you stated to be the essential element, which is sufficient for this discussion) and the concept of molecule, atoms are represented in our mind as points in three-dimensional space. But molecules, which are essentially permanent relations between atoms, are not anymore points, but ordered structures in such three-dimensional space. There you have an emerging feature. While atoms are points, water molecules can be conceived as planes. You can understand this behavior in two forms:
a) Since the atoms in the molecule are performing in a different manner (atoms exhibit physical changes), the original atoms have disappeared, and new atoms appeared with the capability of interaction, which physically perform in a different way. Emergence in this case would imply change, which is not sound, since emergence is about the same elements raising new features. But this is the objective reality.
b) In spite that the atoms in a molecule perform in a different way, our mind is able to approach them as the same elements. This is equivalent to consider that the river you've looked a second ago is the river that you are currently looking, or that the person you are looking at the mirror is the same as the one you looked yesterday. The river has completely changed, physically, but not in your mind. So, in this case, emergence does not imply change but a mental behavior that implies approaching a different thing as if it would be the same. This is a subjective reality.
Even if the mind perceives different things as the same object (we think they are the same atoms, when in fact they are not), it grants them of new features. A molecule can form a plane or a body in space, while an atom can't. A molecule has a length or a volume, an atom hasn't one. A molecule has an extension, an atom hasn't one. Etc. But those are, clearly, subjective features (moreover, if you agree with Immanuel Kant regarding space, which would be a rational-subjective construct; every spatial feature would also be a subjective perspective to approach the environment).
So, emergent features are just illusions given by perception, by our mind that is able to associate some types of change (like eternally changing large masses of H2O molecules) to subjectively created entities (like the static idea of river X). At the bottom, the real issue is not emergence, but permanent change, and how our mind assesses it as if static things would exist.
Following your example, the real issue is how do atoms perform in order to interact; how does interaction change systems, and what does life mean, instead of how life emerges from a bunch of molecules, which is moreover a subjective speculation with a lot of arbitrary and biased suppositions: atoms, molecules, cells would not be changing phenomena, but static objects that when associated in a unique way, are able to reproduce and eat. That sounds quite naive and largely subjective.
Note 1: The same notion from a different perspective: a new feature is just a different idea, which must logically corresponds to a different system. Nothing new here.
Note 2: Complexity is a really confuse term. A complex system is just a system that someone can't understand . But the general systems theory was created precisely for that. So, the term is usually not necessary. It has been used, in my opinion, to justify facts of academic corruption.
 Google for 'complex systems': either complexity is wrongfully associated with common systems (in such case, the term has no reason to be), in other cases it is associated with features of living entities (in such case, it is just plain biology, not a feature applicable to general systems); but in some cases it is related to understanding, which seems more coherent; nevertheless, since the systems theory is precisely a way of dissecting complexity to address simple problems, the term has anyway no reason to be.