In the US, trademark rights depend on use -- not registration. So it's no good to be first to register if you weren't first to use. (Unless you got "dibs" by filing an intent-to-use registration before the other use started.)
There's no way to guarantee that a new name or slogan won't risk infringement, but you lower the risk significantly when you search both registered marks and unregistered (using the internet). When you search, moreover, you need to include not just the phrase you intend to use, but any similar permutations -- including alternate and phonetic spellings of the terms in it. What you're focusing on is the over-all "commercial impression" of the phrase. (As for the hits, you want to not only consider uses by direct competitors, but by any businesses that run in the same channels of trade as yourself.)
The best approach, of course, is to have a trademark attorney use a reputable search firm to do the search and then have the attorney analyze the results. It's usually a judgment call as to how likely a mark is to infringe or not infringe what's found in the searches and it takes experience to know how to make those calls.
----
Note, that it's possible that your example wasn't a true parallel of your actual phrase and the competitor's mark. If the words in common were words that tend to be normal descriptors for your business (and not require a leap of the imagination to connect it to the product, like "grow together" does), it could be that neither of you would have rights in the common elements of the phrases (i.e., anyone could use them). But this sort of thing should be discussed with your own trademark counsel in private, not in a public forum. There are some good trademark attorneys who participate under their own names in the trademark forum whom you might be able to consult without breaking the bank.