Database Mirroring login attempt failed with error: 'Connection handshake failed. The handshake verification failed. State 36.'

This is an issue with the encryption method used on the database mirroring endpoint. In SQL Server 2014 the default encryption type was RC4, but in SQL Server 2016 the new default is AES and it looks like the CU2 update may have removed support for RC4.

To detect and fix this you can run the following on your nodes:

-- Looking at encryption_algorithm - RC4 is deprecated in 2016 CU2+
Select * From sys.database_mirroring_endpoints

Alter Endpoint Hadr_endpoint
 STATE=STARTED
 AS TCP (LISTENER_PORT = 5022, LISTENER_IP = ALL)
 FOR DATA_MIRRORING (ROLE = ALL, AUTHENTICATION = WINDOWS NEGOTIATE
 , ENCRYPTION = REQUIRED ALGORITHM AES RC4)
 GO

After which replication should start working again and you can continue with the rolling upgrade.