It seems that you may have identified a common law holder that certainly has rights in their name despite not having registered with the USPTO. Those rights are typically limited by their market area (geographic area and natural expansion), but in a digital age this analysis can get chewy.
Whenever you endeavor into investing in a trademark it is very important that you conduct the proper clearance due diligence upfront and before you submit an application to the USPTO. In the US, this means searching under both federal (USPTO) as well as common law because trademark rights stem from use in this country NOT registration. This means that acquiring a federal registration does not necessarily mean that you are not infringing on another's intellectual property. See the link below for a detailed explanation of the due diligence process.
You obviously need to have a proper analysis done and not a hypothetical one. I suggest that you consult with a lawyer in private and discuss your objectives in more detail. You can start by calling around to several for a free phone consultation, get some insights then pick the best fit to work with.
DISCLAIMER: this is not intended to be specific legal advice and should not be relied upon as such. No attorney-client relationship is formed with the law firm of Natoli-Lapin, LLC on the basis of this posting.
The senior user of a trademark, even if unregistered, could sue a junior user of the trademark selected by the junior user is likely to cause consumer confusion. The issue here is whether your trademark would cause consumer confusion. That is hard to evaluate based on the limited information in your question. Companies spend millions of dollars to litigate likelihood of confusion issues, which involve judicial consideration of a wide array of factors, such as the extent to which the companies compete for the same customers, in the same geographic industry, for the same or similar products; the extent to which the mark of the senior user has become famous and has acquired "secondary meaning", the extent to which the senior user has used the trademark across a diverse area of product lines, and the extent to which the two companies use the internet to operate----will customers looking for the senior user be diverted to the web-site of the junior user. Without knowing much more information, I cannot begin to advise you on what you should do.
One thing is clear---if you want to use this new trademark, you need to retain legal counsel to conduct a trademark clearance/likelihood of confusion analysis. And you need to be prepared for the distinct possibility that your attorney will not be able to bless your use of the trademark.
Finally, even if you could successfully register the trademark with the U.S.P.T.O., this would not change my analysis. In the US, trademark rights arise from use in commerce, not registration. Registration is very valuable in litigation, but in a situation like this what matters is whether there is likelihood of confusion. As to that issue, you need to retain legal counsel. But no matter what your counsel concludes, there will always be a risk that the senior user will sue you for trademark infringement. If that happens, you will have an expensive problem on your hands because trademark suits can require hundreds of thousands if not millions of dollars to defend.
Of course the other company CAN file a lawsuit. Anyone can. Your real question is whether they can win. And, I must tell you that we cannot give you a specific answer here since you are not a client. We can only give you general advice along with a recommendation that you hire an attorney to get that specific advice.
The question a judge would have to decide is whether or not your using "Leaf & Wool" on whatever products or services you use it on concurrently with the other company using "Leaf Avenue Paper Company" is likely to lead to confusion as to source of those products or services. There are many factors that are taken into account. You only consider two of those factors: similarity of the marks and similarity of the goods. You have identical goods and a similar first word in each Mark. There are from 5 to 11 other factors that are taken into account depending on the particular judicial circuit in which the analysis is made. So that these factors are considered in the manner that is appropriate for your judicial district and the judicial district in which the prior company is located and at the US Patent and Trademark Office, if you are going to file an application to register your trademark or service mark, you should hire an experienced trademark attorney. There are many good ones here on Avvo. Use the Find a Lawyer to search for one or look at the answers and pick the attorney that you think you would like to work with the most.
Most of us offer a free initial consultation, although for what you need a more detailed analysis will likely be most appropriate.
I am not your lawyer and you are not my client. Free advice here is without recourse and any reliance thereupon is at your sole risk. This is done without compensation as a free public service. I am licensed in IL, MO, TX and I am a Reg. Pat. Atty. so advice in any other jurisdiction is strictly general advice and should be confirmed with an attorney licensed in that jurisdiction.
Short Answer: Choose another name if you can
Trademark rights require use, not registration. By using a mark that is not registered you acquire what is known as "common law' rights in the mark. You get more robust, expanded rights in the mark by registering it but that is not a requirement. So in this case, the prior user can sue you even though they are not registered. I would advise that you consult an attorney to get a better picture of your rights and option. Good Luck