Let $z$ be a complex number, and $z^*$ be the complex conjugate. Is it possible to write $z^*$ in terms of $z$ while only using elementary functions like polynomial terms (complex exponents are allowed), exponentials, logarithms and such.
So, $z^* = z - 2\operatorname{Im}(z)$ is not allowed because $\operatorname{Im}(z) = (z - z^*)/2i$ references $z^*$ also and this would be circular. However, if you can write $\operatorname{Im}(z)$ as a formula of $z$ without referring to $z^*$ then, this would be okay.
Similarly, $z^* = |z|^2 /z$ is not allowed less you can write $|z|^2$ in the same way requested above (without referring to $z^*$ itself).
I have an intuitive feeling that this is not possible but can't figure out how to prove it.
No, this is not possible, principally because elementary functions and compositions, sums, and products thereof are complex differentiable, whereas the map taking $z$ to $z^*$ is not complex differentiable since, for instance, if we try to differentiate at $0$ we see that $$\lim_{z\rightarrow 0}\frac{z^*}z$$ does not exist, since this quantity is $-1$ everywhere on the imaginary axis and $1$ everywhere on the real axis, so lacks a limit at $0$. Indeed, $z^*$ is not complex differentiable anywhere, so you can't even write it in elementary terms on any open set.