What makes the Discrete Logarithm Problem hard?
It is true that you have in the worst case $\operatorname{ord}(Z^*_p)$ values to test. However, the complexity of a problem is actually measured according to the size of the input of the problem in computer representation which is binary.
Here the inputs to our problem are h and p. These two are integers both of size $log_2(p)$ at most in computer binary representation. And the algorithm would take $\operatorname{ord}(Z^*_p) = p$ iterations. However, $p = 2^{log_2(p)}$, so we can clearly see that the number of iterations required is actually exponential to the size of our input of the problem. Which is why the discret logarithm problem is hard.
When you usually see complexities of the form $O(n)$ or $O(log(n))$, we actually assume that the size of our problem is $n$ in computer representation, without explicitely saying it.