A Cease and Desist letter is a good idea, but I would have a lawyer draft it. It shouldn't cost that much money and your attorney would be careful not to put anything in there that would force you into Court unless you wanted to. Sending legal looking letters on your own is a bad idea, you might accidentally run afoul of laws related to frivolous lawsuits and torturous interference.
Something like that shouldn't take more than a couple of hours of a lawyers time and your company probably already has retained a business lawyer, anyway. If you really want to save time, search for standard Cease and Desist letter language, there must be examples all over the internet, probably some specific to this type of action, rework it to your case and give it to your lawyer for review and clean up.
If you do file a case, coming up with damages you can defend might be difficult, but you should try to estimate, anyway. That figure could be used in the Cease and Desist letter to help push them over.