The second point first... your objection is perfectly sensible, and if Paul only wanted to consider rectangles, he should have said so in the question. In fact, forming the fence into a circle - or to be more precise, a semicircle - will give a larger area. (A square, on the other hand, is a special kind of rectangle and therefore is not excluded by Paul's method of solution, though it doesn't happen to be the right answer in this case.)
The restrictions on $y$ arise from considering the physical meaning of the problem. You can't (in this question) have a length less than zero for the vertical side, so the minimum possibility is $y=0$. You can't have a length less than zero for the horizontal side either, and a little thought will show you that this means $y$ can't be greater than $250$.
I think perhaps you are not recognising that "no sides to the fence" is different from "sides of length zero".
Let the width of the base be $x$ and the height of the box be $y$. The base is a square so its area is $x^2$. Then the volume of the box is "base area times height", so the volume is $V = x^2 y = 40 ft^3$.
The area of the base is $x^2$, so the cost of the base is $0.31 x^2$.
The area of each side is $xy$, so the cost of each side is $0.05 xy$, so the cost of all four sides is $4 \times 0.05xy = 0.2xy$.
The area of the top is $x^2$, so the cost of the top is $0.19 x^2$.
So the total cost is $C = 0.31 x^2 + 0.19 x^2 + 0.2 xy = 0.5 x^2 + 0.2 xy$.
Since $x^2 y = 40$, we have $y = 40/x^2$, so $C = 0.5 x^2 + 0.2 x\times\frac{40}{x^2} = 0.5 x^2 + \frac{8}{x}$. This we can optimise using derivatives.
Advice for similar problems:
A useful strategy is to give names (ie pronumerals) to all the unknowns in your problem. It is easier to talk about things if they have names. In particular, you can start writing down equations.
When contructing equations, a useful strategy is to organise the information you have on the page so that it is easier to see the connections. (I put each part of the box on a separate line, for example.)
Finally, if you know how to do a problem a certain way (using derivatives of a single variable, for example), then once you have everything written down, you can think about the goal you want to get to and see how to get there. We had to get to an equation for $C$ in terms of only $x$ or $y$, so we had to think of a way to make either the $x$ or the $y$ into something in terms of the other. The only other information we had was the volume, so it seemed like a reasonable thing to try.
Best Answer
Area $\mathcal A=5000=lw$
Since you assumed here that $w>l$ the price is $P=10\times(2l+2w)+4\times(l)$
When you substitute $w$ you get $P=24l+20w=24l+20\times\frac {5000}l$
You want to minimize the price, so let's calculate $\displaystyle P'(l)=24-\frac{100000}{l^2}$
$P'(l)=0\iff l^2=\frac{100000}{24}$ gives you $\quad l\simeq64.55\; m\quad w\simeq77.46\; m$