How can I make a raw vegan shrimp paste substitute?
As far as I know, shrimp paste is ground shrimp fermented with a lot of salt. You may have a hard time replicating this exactly with easy-to-find vegan ingredients, but I think what might work well as a substitute is a mixture of miso and dried seawead or kelp powder. The seaweed would give you the fishy taste and the miso - which is salted, fermented soybean paste - would give you the funky salty part. 

I'm not sure if you consider miso raw, because it's often pasteurized, but you might find unpasteurized miso at a health food store or Whole Foods. It wouldn't be as "safe" as pasteurized and might have other stuff growing in it. If you want to make sure it's raw, you could also make the miso yourself. I won't tell you how to do that here, but there's sources online. You can also get you sick if you ferment it yourself and don't pasteurize it. 

Another vegan alternative, but not raw - is to get some Taiwanese meat substitutes. I live near an importer in NYC that sells tons of stuff online, include shrimp and other fish substitutes. In my experience they are very fishy tasting, but that might work for this application. Here's a link to their seafood section. http://www.maywahnyc.com/SearchResults.asp?Cat=1819