Nick,
The Scott catalog #s for your stamp from top to bottom are
875
712
654 or 655 (you will need to measure the perforations)
874
A116 (design number, cannot determine actual catalog # from your scan)
A88 (same note)
All except 874 (1c Audubon) are NOT sufficiently well-centered enough to warrant grading. The 874 block you have is extremely well-centered, but has war perfs. It may get a pretty good centering grade, buy in MY OPINION, you would be hard pressed to sell it at a premium with those war perfs.
I should note that I am not a big fan of grading common US stamps, so you may want to keep my bias in mind.
Encapsulation is an option and costs extra.
Foreign stamps may or may not be more valuable. It all depends on what you have, and if there is a demand for it. Barring a rare variety on the last 2 (I can't tell from your pics), the US stamps you show are all either minimum catalog value or very minor premium. I'm not sure, but I'm guessing the block of 4 of #712 you found on
ebay is for a PLATE BLOCK of 4. You have the basic block of 4, and that will catalog for a little over $1 assuming it is never hinged.
Hope this info helps.
Enjoy your stamps!

Kim