Try consulting with a nutritionist who is vegan or vegan-friendly. They can help you find a variety of foods that would be OK for you. There is a HUGE variety of vegan foods out there. Health food stores are a good place to find a lot of them.
Regarding protein, don't be worried. Pretty much the only way to become protein deficient is to actually be starving.