If I knew the exact location of my robot and have an accurate map (for eg. an occupancy grid map) of the environment beforehand, how can I compute a measure of how well the laser scan data agree with the given map ?
You should look into localization algorithms. A good source is the book Probabilistic Robotics - W. Burgard, D. Fox and S. Thrun.
If you just want to compute somehow how well it agrees you could try to compute the Root Square Mean Error of the closest point of your measurement to the point in the occupied square in the grid describing the map, given an accurate robot position and map description.