Two obvious reasons to try polynomial method:

1) The problem may be formulated as vanishing/non-vanishing of some polynomial.

2) The problem is similar to one of already solved by polynomial method, say, to one of problems considered in fundamental Alon's article http://www.tau.ac.il/~nogaa/PDFS/null2.pdf

Some hints, based on my own impressions:

3) The problem solvable by polynomial method is rather sharp, then asymptotic in nature. So, I doubt that Freiman's theorem may be proved on this way, while Cauchy-Davenport is ok. Often slightly weaker results are obvious (for example, in Cauchy-Davenport, if we replace $|A+B|\geq |A|+|B|-1$ to $|A+B|\geq (|A|+|B|)/2$, it becomes obvious. If we replace $d$-choosability of a graph with degrees about $2d$ to $(2d+1)$-choosability, it becomes obvious.)   

4) Some algebraic structure must exist in the problem. Say, planarity of a graph is not very algebraic condition:) Further update: my intuition got slightly wrong here. There is a polynomial proof by Ellingham and Goddyn that $r$-regular edge-$r$-colorable planar graph is edge-$r$-choosable. The reason with parity is quite cute. 

5) be careful on wether you prove what is true or even more. Say, CN is often applied for graph choosability, and I do not know applications to graph colorings different from proving choosability. Thus, if your graph is not a priori d-choosable, it can hardly be shown with CN that it is d-colorable.

I may remember some other impressions later.