Some entertaining back of the envelope calculations.

Focusing considerations

Suppose the beam has a waist size of 1 m here on earth. We can determine how large the beam will be at Mars using Gaussian beam formulas. I'll assume a wavelength of $1 text{ $mu$m}$, though I'm not sure what wavelength is needed to liberate CO$_2$ molecules (but I do know that CO$_2$ lasers can generate $1 text{ $mu$m}$ light so this is a good hint that the right wavelength will be in this ballpark). The closest Mars comes to Earth is about 80 Mm

begin{align} w_0 =& 1text{ m} z_R = frac{pi w_0^2}{lambda} approx& 30 text{ Mm} d_{Mars} approx& 80 text{ Gm} end{align}

The size of the waist on mars would then be

$$ w(z_{Mars}) = w_0sqrt{1 + left(frac{z_{mars}}{z_R}right)^2} approx 30 text { km} $$

Ok this is good because Mars is much bigger than $30 text{ km}$ across so this means the beam won't diverge so much that most of it misses Mars.

I think this answers the first part of your question about focusing distance.

Will the 3.5 kW laser have an impact on Mars' atmosphere?

Can a 3.5 kW laser have an effect on Mars? For this is I really personally can't contribute much. We can calculate the number of photons coming out of this laser per second (photon flux $N$)as

$$ N = frac{P}{hbar omega} approx 2times 10^{22} text{ s$^{-1}$} $$

One mole is $approx 6 times 10^{23}$ particles so if every photon in this laser liberated one CO$_2$ molecule the laser would liberate one mole about 30 seconds.

This page estimates there are $10^{44}$ particles in Earth's atmosphere. Not all of those particles are CO$_2$ but probably at least 1% are so we still need to generate $10^{42}$ CO$_2$ particles to approach earth like atmosphere.

It would take this laser about $10^{20} text{ s} = 3 times 10^{12} text{ years} = 3 text{ trillion years}$ to do this.

And that's assuming perfect efficiency. This will likely be increased by orders of magnitude due to losses in the atmosphere an inefficiency in the CO$_2$ generation procedure.

Is it hard to hit Mars with a laser?

Regarding the tracking problem.. I'm not an astronomer so I don't know how tricky it might be. The diameter of mars is 7 Mm so the angular size of mars is about 80 microradians. The earth rotates at a rate of about 70 microradians per second, so I guess mars moves by one "size of mars" per second. Here I'm assuming the angular motion is due only to the rotation of Earth. My guess is that this dominates apparent motion due to the relative linear motion of the two bodies but I don't know that this is the case.

In this case Mars will travel about 16 mrad in 3 minutes time (time it takes like to get to mars) so you need to predict the end of a trajectory which is 16 mrad long with a precision of 80 microradians, or about one part per 200. This doesn't seem too bad as a tracking problem. You can watch the trajectory over a few nights and see how much variation there is a from a predictable "Earth's rotation" trajectory and see if there are fluctuations on this order.

What I will say is that stabilizing a telescope to the 10s of microradian may be at the limit of what is "easy".

But again, I'm not an Astronomer. An Astronomer would be better suited to answer things like how easy it is to make a stable telescope and what constitutes an easy vs. hard tracking problem.

One major difficulty is that there would be no feedback to know if you'd hit the target or not, at least not until your terraforming is completed after 3 trillion years and the resulting intelligent species can send signals back to you..

edit: 3.5 W or 3.5 kW? Not sure which the question is asking about, it is inconsistent. A 3.5 W continuous wave laser is high power in that it can easily blind you and it is moderately high power for atomic physics applications with which I am most familiar. It is maybe 3 orders of magnitude more powerful than a laser pointer. However, as far as lasers go 3.5 W is really not that much. That is why I went with 3.5 kW. 3.5 kW would be a very low laser power for industrial laser cutters, for example. All of that said, 3.5 W would be pretty high power for a hobbyist to have at home.