How does "headers first" affect BLKxxxx.dat structure?
To the best of my understanding, it's just that the blocks are stored in a different order. Headers first synchronization makes use of parallel downloads and the blocks are downloaded (and then stored) out of order. It used to be the case in older versions that blocks were downloaded and then stored in order, so that's whey they added the comment to the README. 

I believe it doesn't change the structure of how any individual block is stored, just that they are now likely to not be in the proper order.