Ich hab intern eine VM mit einem Uralt System die ich manchmal für diverse Testzwecke hochfahre. Wenn ich mit dieser SSL Verbindungen nach außen aufbauen möchte, krieg ich auch gerne mal die "unable to get local issuer certificate" Meldung, weil der lokale Zertifikatsspeicher mit den Root-CAs etc. hoffnungslos veraltet ist und die Authentizität des entfernten Zertifikats daher nichts verifiziert werden kann. Das wurde mit dem großen Zertfikatswechsel bei Letsencrypt vor zwei oder drei Jahren dann nochmal erheblich häufiger.
Will sagen: Für mich klingt es so als wäre Dein Set an Root CAs veraltet.
Somit kannst Du entweder schauen, dass Du die auf der Paperless Maschine auf Stand kriegst (Paket heißt meistens zb. "ca-certificates" bei vielen Distributionen) oder Du bringst Paperless dazu, auf die Verifizierung des Zertifikats zu verzichten.
Wenn es Paperless zulässt, wäre auch die Verwendung von unverschlüsseltem IMAP denkbar - muss man dann selbst abwägen ob man das möchte.