Error code is 0x80131500 when applying SP4 to SQL Server 2012
Mystery solved. I have found out that the network segment between the nodes of the AG had File and Printer Sharing disabled. Only Sql traffic was allowed.
Re-enabling that on both nodes of the AG for the time it takes to apply the patches on both nodes allowed the needed communication between them.

Just another reminder that you should always check the simple things first when you have a problem.

Have a great day
Richard