Is the paste safe to use?
It's hard to say with any certainty -- we can't smell the paste, you haven't said specifically what the paste is (product name, brand, etc.), and there can be a lot of variation in how different people perceive the same odor. Asking for an opinion from one or more people around you could help.
That said, you're the one who is considering eating the product in question, so if it smells bad or unappetizing to you, toss it. In general, if there's a question about the safety of a food, it's better to be safe than sorry. And even if the food in question is safe, there's no reason to use a product that you're pretty sure you won't enjoy.
Keep in mind that there are some strong odors that are less than lovely by themselves, but which are still delicious in small amounts or when mixed with other ingredients. Onion and garlic can fall into that category, and fish sauce isn't great either.
You could call the manufacturer and see what they say about it -- they might send you a coupon for a new jar if you're willing to give the product another try. Or you could take it back to the store and ask for a refund or exchange.
Trust your instinct -- the nose knows.
