As for brass, you will probably be stuck with whatever an individual supplier has on hand or can get.  30-40 brass is probably on the "seasonal" or some other short run list.  It is apparently not an every-day production item.  If you buy bulk brass, either Winchester or Remington, some of the cases will need trimming (slightly) to true up case mouths.  All should be at least neck-sized, de-burred & chamfered before the first loading.

Get a Wilson case gauge for 30-40 and use it on every case each time you reload.  Midway has them for about $30.  They will never wear out.  The Wilson gauge will tell you when you need to trim your fired cases.

Following is a link to Buffalo Arms as a source of cast bullets. 

(You need to Login to view media files and links)

Hard cast bullets will not turn your Krag into a Pope-barreled target rifle.  But if you experiment with them, you can get results that will keep most of your shots in the 10-ring at 100 yards, assuming that your eyes & the Krag sights are up to the task.  The Gardner's Cache site is selling 500 bullets.  If they don't work well, you may be stuck with 450 that you have not much use for.  Buffalo (& others) sell boxes or bags of 50 or 100.  The bullets intended for the .303 British work very well in most Krags.  Try several styles & sizes.  Maybe even the .314 bullets on the Buffalo site.

Gas checks are helpful if you are trying to shoot faster than about 1600 fps.  But they must be seated squarely.  If not, a flyer is guaranteed.  Never seat a gas check bullet with the gas check below the case neck, extending into the main case.  If the gas check gets loose, you could have all sorts of problems.

Guys who shoot a lot of lead bullets in old military rifles use mild loads of Re-7 or 3031 or one of the specialist powders.  If you have 4064, you can start with that.  You will see recommendations for loads with SR-4759 or for one of the #2400 powders or for 4227. Be careful there!

The Krag is a very easy cartridge to handload for. I shoot predominantly cast bullets from mine - the Lee C312-185-1R sized .312 cast from 100% wheel weights. Powder charge is 19 gr of SR 4759 which is an excellent cast bullet powder. As the above post stated, watch for seasonal brass and buy in bulk. I use a .303 British neck sizer to neck size only. The brass will last a very long time that way. For pig hunting loads, I use H4350 under either a 180 gr Hornady round nose or the 220 gr Hornady round nose. These bullets are not as accurate as cast as they are a bit undersized for my bore.

- I'm having a real tough time finding some 220gr cast lead .30 cal bullets sized above .308. My Krags barrel slugs to .311, so I guess I need .311 or .312.

Did you slug the throat (leade)?  If not, verify the groove dia there is also .311"  Also, get a sample .311" or .312" bullet & seat them is a case to make a dummy round.  Verify the larger bullet, seated in a case, will easily chamber. \

Get a copy of a good loading manual.  I prefer the Lyman 49 and it covers both jacketed & cast bullet loading techniques & data with a variety of components.

- What powder is good for a mild load for punching paper?
Any of the 4895 powders work.  For cast bullets, consider 2400.

I've read even some medium loads can crack the bolt on a Krag.  I haven't heard this but I suppose anything can happen.  Have a competent gunsmith, familiar with Krag actions, check yours if you have any doubts about it.

- Do I need to trim rifle brass in a bolt action after every firing?

Maybe not after every firing but perhaps every 2-3 firings.  The Lee case trimmer system is the cheapest & easiest system to use.  Measure cases after each firing to make sure they do not exceed max case length.

- Remington or Winchester, which .30-40 Krag bass is better? Apparently some prefer Winchester but Remington is all Midway USA has in stock.

I prefer Winchester but Remington is fine as well.