||I've spent almost 12 hours in Paris, so I am clearly an expert.
Train station lockers are probably more expensive than you would think, but other than that they are quite convenient.
As for site seeing, just across the street from Gare de l'Est is a delightful French restaurant that looks and functions exactly the same as McDonalds. However, it is a French restaurant, and clearly is not some USian corporate chain devoid of soul and character. This is because it is French. I recommend combo #2.
Also, watch out for all the dog shit. Parisians seem to not feel the need to clean up after their pets.