Assume the 1994-gon does in fact have all its vertices on the lattice points.  Then the 3988-gon must have its edges coincident with the grid lines.

Imagine walking along the perimeter of the 3988-gon.  Your steps will be north, south, east, or west.  A perimeter is a closed path so you will eventually return to where you started.  But for that to happen every north step must have a corresponding south step.  Similarly every east step must have a corresponding west step.  Then the total number of steps, and the length of the perimeter, must be even.

Why alternate slopes will not work: (Why the perimeter will be odd)

In my original proof I assumed that all slopes were 2:n, as implied by the formula sqrt(n^2+4).  Then by calculation the perimeter is odd.  But you are right there are some lengths that can have some different slopes.

First consider odd edges, like your c^2=85.  No matter which composition you use, one side must be odd and one side must be even to total to an odd hypotenuse.  Making a substitution will not change the parity of the perimeter of the 3988-gon.

Now consider even edges, like your c^2=1300.  The sides must be either both odd or both even to total to an even hypotenuse.  Again, making a substitution will not change the parity of the perimeter of the 3988-gon.  Thus all possible 3988-gons have an odd perimeter. 

This contradicts the result showing that if all the vertices are on lattice points that the perimeter is even.  Therefore there must be at least one vertex not on a lattice point.