The linked paper is titled unfortunately, at least as regards the current conception of the word "random." The whole point of Benford's law is precisely that it doesn't hold when integers are drawn uniformly from a range that, like yours, ends at a power of $10$: a well-designed pseudorandom number generator should give numbers with asymptotically exactly a $\frac{1}{10}$ chance of each leading digit $0,1,...,9$ in decimal notation.
Benford's law applies not to properly random sources of data, but to data produced by certain real-life random processes. One simple characterization of data that obey Benford's law is as those produced by processes that exhibit more-or-less exponential growth, such as populations. Such processes produce uniformly distributed logarithms of data points, but this uniform distribution gets splayed out into the characteristic Benford's law upon exponentiation.