Two's complement max with a different base
As long as different 4 digit numbers in base b represent different decimal numbers, the particular notation one uses is not relevant to see how many integers can be represented. I'm not sure how the two-complement notation generalizes to the b-complement notation, but if the above property holds, then clearly there will be 9^4 representable integers.

My guess is that the first digit does not need to be 0 or 8, it can be any digit. That is, I think one could use the following encoding:

0000 0
...
4444 MAX
4445 MIN = -MAX
4446 MIN+1
...
8888 -1