I've been making a soup that has an onion + garlic + carrot + celery + flour base, and then chunks of sweet potato and potato as well as barley added. I've been spicing it with salt, pepper, garlic powder, and basil. Now I want to substitute paprika for the basil. Would that ruin the soup?
Paprika brings out the best in savory flavors. I'd go with something a little hotter to compliment the sweetness of the sweet potato - but not too hot, or you'll loose the regular spuds.
Go for a barbeque or curry: both of those will go well with the veggies you're using. Actually, your best bet is to experiment and try lots of different spice combinations. Soups are very versatile.