I'm looking for something that can hold ~6 stones, a stone holder, and a few small accessories. I'd also like it to be soft (i.e. no tool boxes etc), and somewhat portable.
Shooting bags are designed for ammo boxes (rect, heavy - remind you of anything?) that are roughly the same size as stones. They will also have pockets for extra "stuff". Easy to carry and most have shoulder straps. They are available from many manufacturers and vendors. I posted an easy one.
Note: for searching they are usually called "range bags".
Most shooting supply retailers will also have small pelican cases for more protective transport.