Thanks a lot CosmicDan. I know that method, and, for now, I am not blocked on Gapps. But, IIRC, there are quota on the amount of device 'registration's (I have 2 now). For other custom firmware (GZOSP) it looks like it helped to simply edit the build.prop fingerprint in /system to get 'Certified'. Actually, GZOSP was 'Certified' and stock was not . However, for Treble AOSP, I could not get this to work. Maybe one needs to hack other .prop files (like in /vendor) or maybe I miss something? Also, for my Treble AOSP tissot, the GSF Device-ID registration succeeded, but, the Play Store nevertheless still says 'uncertified'. As said, it is (as is the safetynet cts) a minor issue because, apparently, I can use Gapps just fine.
I guess changing the fingerprint will fix it, we're talking about it internally (there's a few props) but I don't actually know if it causes any problems if it shows as Uncertified.