How can an adversary use Mac(.) with a new key to compute a tag although this is not a query to Mac oracle?
In modern cryptography it is generally assumed that algorithms are public and only the key is kept private.
Thus, the adversary can compute $\operatorname{Mac}(k', m)$ for any key $k'$ and message $m$.

The oracle $\operatorname{Mac}_k(\cdot)$ in the experiment allows $A$ to additionally receive valid macs under the challenge-key $k$ for which it is supposed to forge a valid mac (for some message $m^\ast$ that it has not queried from said oracle).

The same goes for the second part of your question: the algorithm is public, so $A$ can run it on any input.