After 7 years, I had enough of the eraser problem. This year every student brings their own pencil and eraser. It was a little hassle at first... but they get used to it. The problem is that they don't care when it is not THEIR own pencil...(if it falls on the floor, so what?) but it is amazing how much better they keep track of them when it's their own.
The PE problem, have each student tape a "flag" on their pencil with their name on it, then keep a can for that class in your room, with the pencils in it.
Lastly - search for FREE stuff!! Call the paper companies in your area and ask for "scraps" (their idea of scrap is a treasure to me!) I got huge(3 ft by 4ft) sheets of paper, as many reams as I wanted from one company!! Some frame shops will give you small pieces of matboard. And, definitely send home a note to parents asking for items you could use.