How "coplanar" is a set of points?
Option 1: Use least squares fit to find the closest plane.  Then, measure the average squared error (the sum of the squared residuals).

Option 2: Use robust regression instead of least squares.  Or, use RANSAC.  These will handle outliers better.

All of these run in polynomial time.