Which of these two functions has a higher order of growth/complexity?
You have gotten wrong the 1st property, that $2^{\log^*(n)} \sim ~n$.  This is not the case.
The notation $\log^*(n)$ is the iterated logarithm, and the iterated logarithm grows much much slower than the logarithm, so $f$ grows much slower than linearly.