Devastation affects settlement income but shouldn't affect fertility. If you want to boost your fertility to boost population for city upgrades then build farm buildings when they're available.

I think you should work more on your trade, or conquer then chop heads when you take a settlement.