I wouldn't be surprised if eating in a more paleolithic manner would help curb the desire to smoke. However, I believe exercising regularly would be an even more effective deterrent. Basically, I don't think a person can continue to both smoke (at least not heavily) and exercise with any intensity on a regular basis. Something would have to give... either you'd quit smoking (or smoke considerably less), or quit exercising.
Probably why you don't see many people light up after running a marathon...
