Let $X$ be a smooth protective variety, or just a smooth Kahler manifold. Is it possible to have two curves $C_1$ and $C_2$ in $X$ such that their difference in $H_2(X,\mathbb{Z})$ is a nontrivial torsion class ?

Yes, this is possible. For an example of a CalabiYau threefold with such differences of curves, see my paper with Pavanelli http://arxiv.org/pdf/math/0512182.pdf. I am sure there are much simpler examples, however. 


This is off the top of my head, but I think that the canonical class of the Enriques surface is a torsion class given by the difference of curves. Every Enriques surface is obtained from a rational elliptic surface by performing logtransforms on two of the elliptic fibers. The class $F_1 + F_2  F$, where $F_i$ are the transformed fibers and $F$ is a generic fiber, is then 2torsion. 


Every divisor class $D$ on a surface is the difference of two smooth, connected curves. Choose a very ample divisor $A$ and an $n$ so that $D+nA$ is also very ample. Then $(D+nA)nA=D$ so $D$ is the difference of two curves. They may be chosen smoothly by Bertini's Theorem. ADDED LATER: They may also be chosen to be connected. The Lefschetz hyperplane theorem shows that hyperplane sections of surfaces are connected. 

