Our shared HP LaserJet printers recently stopped working in exactly the same way you describe, i.e. "Not responding" message in the client's queue and the same CUPS log entry on the server. The printers are shared on a 10.11.6 system with Server.app 5.1.7. The shared printers had been working fine for months. I tried the following troubleshooting steps, in order, without success:
• stopping and restarting "Printer Sharing"
• stopping and restarting CUPS
• un-sharing and re-sharing each printer in "Printers & Scanners"
• restarting the entire server
• deleting and re-creating the printers on both the server and the client
One possible lead: In our case, the problem started on the same day we replaced our server's primary SSL certificate. I can't be certain that that's related, but since the CUPS error message mentions encryption, my current theory is that this has something to do with it.
I still don't have a solution, so I've had to resort to reconfiguring all clients to print directly to the printers instead of queuing through the server.