It's very easy to imagine that as being part of the inner mysteries of a mystery religion: https://en.wikipedia.org/wiki/Greco-Roman_mysteries
Now turning lead into gold is pure 100% unmitigated magic, because we know a lot more stuff. But if we didn't know that stuff, it would not be an obviously magical belief.
Alchemy is not useful, but what you said here is not a magical belief. All elements were in fact created through the fusion of lighter elements before them through nuclear transmutation. Stellar nucleosynthesis is the natural process creating the variety of elements in the universe.
In other words, we do conceptually know how you can turn lead in to gold, and even heavier elements than gold have already been artificially created.
Wikipedia has a periodic table with the origins of each the elements.-1
1-https://en.m.wikipedia.org/wiki/Stellar_nucleosynthesis#Key_...
I'm aware that there is a lot of quackery out there but there are a lot of mysteries about the nature of existence, of consciousness, of the beginning and end of the Cosmos still.
This is understating the issue quite a bit. Don't forget that the point of science is to test things in a robust manner, which at this point in time has been done for the things you mention, but in Newton's time they hadn't been.
I think Newton being the "Last Magician" fascinates/frustrates people because currently we (think) that there is such a clear divide between scientists and mubo-jumboists, the latter perceived to be rather idiotic. In fact, most topics have pretty clear labels classifying them into one or the other: diffraction - science, tarot - MJ, etc. How could Newton, the epitome of reason and the greatest scientist ever lived, dabble in the latter? Of course, the labels were not so clear at his time.