I would like to make umeboshi makizushi, but I don't have access to shiso leaf which is traditionally paired with the umeboshi. Is there any acceptable substitute for the shiso that is more readily accessible in the US?
Shiso is in the mint family. Stick to that area and you'll be fine, even though nothing will be exactly right.
Peppermint leaves, lemon basil or Thai basil will all give a nice look and a pleasant flavor, even if it won't be quite the same. A combination of mint and and Thai or Holy basil might be your best bet. A tiny, tiny drop of toasted sesame oil will get you even a little bit closer.
I just read from a totally unknown (to me) source that lemon thyme hits a lot of the same notes, but obviously that would look completely different. Again, perhaps a combination will get you closest.
There are basically no substitutes for shiso. Yes, it's in the mint family, but that doesn't mean much; you can't replace turnips with mustard, even though it's the same species!
There is, however, one unexpected source of shiso that may be of use: a very closely related herb, Vietnamese perilla, is used extensively in Vietnamese cooking and can be found from groceries that cater to the Vietnamese community. In Australia, it's next to impossible to find Japanese shiso (I'm aware of one grocery in the country that stocks it, and only sporadically), while the Vietnamese community is large enough that it's reasonably straightforward to find.
As a side note, Koreans also eat a variety of perilla, but despite a deceptively similar appearance, it tastes quite different — more harsh and peppery — and is not a workable substitute.
Did you also look for "sesame leaves" ;)? Thats how you would find it in Germany at least. On a side-note: my korean mother in law grows them in her garden in frankfurt, so depending how urgently you need them, just grow them yourself.