I mean, since E = mgh, you can get the same energy storage capacity with a less deep hole if you use a heavier weight. And you can get a heavier weight either by using more expensive material (why use a cheap one? it's not like it's going to wear or anything), or a larger hole.
I'm not sure what determines the cost of digging a whole, but I suspect depth matters more than area.
Also, does the shaft has to be vertical? You could dig it with a sharp slope, and put your weight on rails. That would make the shaft longer for the same depth, but it would probably be easier to build and maintain.