You don't mention any Xrays to check for IVDD or Spondylosis in his back which could cause neurological damage impacting his ability to feel or control his bowels. My Lab girl had both and had fecal incontinence. Truthfully though, we cannot be sure if it was the neuro. damage or the pain meds that caused her incontinence.
Some of what you describe does sound like cognitive dysfunction.
Good luck. At least with fecal incontinence the poopers are easy to just pick up and put outside. One thing that did help our girl a bit was a high fibre food that bulked up her stools so she could feel them coming on sooner and ask to go outside in time. Ask your Vet. Imodium would do the same thing and is safe for Labs but ask your Vet. Good luck.