The scale is not the issue to be doubting. It's the amount of variety.
Suppose I build an algorithm that puts a random color in each pixel of an image. The algorithm will take longer to solve for a larger image, but it's not more complicated to devise the algorithm. It does the same thing at coordinate (1,1) as it does at (1000,1000): pick a random color.
Granted, that's not a worthwhile algorithm to make because there would be very little use for an image with randomly colored pixels, but that's beside the point. Hello Games have already shown that their algorithm is capable of making trees and lakes and dinosaurs and stuff, so there's no reason to assume that it couldn't do the same across an entire planet.
But where it gets to be more work is adding more variety to the kinds of things that can be scattered about the worlds. It's easy to say this animal is blue and that animal is red, or this animal is at X location and that one is at Y place, but that's boring. It's harder to say a more interesting thing like this animal has four legs and that one has eight. This animal lives in burrowed tunnels, and that one lives in the trees. This animal has one female per pack and that one is evenly split on genders. This animal is a carbon life form and that one is silicon. This animal needs to water every hour, and this animal stores water in its hump for a week, and this animal is poisoned by water. This animal has object permanence and this one does not. This animal stabs its prey and waits for them to die before eating them, and this one waits for others to kill its food or for its food to die by itself, and this animal eats fruits from the tops of trees instead of other animals.
There are a lot of things you can take for granted in a "random" creature which start to seem repetitive after a while. If all the animals have only two eyes, that's a missed opportunity. If all the land animals have four legs, that's a missed opportunity. Or if none of them live in trees, et cetera. So there is legitimate concern that there won't be enough variation, because variation takes work. But simply putting dense detail in each inch of the planet is not impossible, or even hard given enough RAM.
It depends on what you mean by random. You can bet they make plentiful use of their PRNG. For the end-user, repeated visits to the same sector will net the same thing, but on first visit it will seem random in arrangement. After all, if the game were truly random, it would be rather like the TV static in appearance and sound. Nothing of note could be made out from the visuals or audio.