The many answers to the original question are a testament to Apple's messiness when it comes to code signing and provisioning.
Short answer:
I could launch successfully again on device by simply deploying to another device, then going back to the device where it first failed: same AppleId, same OS (iOS 12.4.1 on both devices, macOS Mojave 10.14.3 on macBook), same project, same Xcode 10.1. No need to uncheck "debug executable" in the project scheme.
Long answer:
The problem is hard to catch basically because the error is non-descriptive. Judging by the answers posted, it looks like there might be different causes, probably related to some configuration for the AppleId being used for the signing.
One way to narrow down the search is to use Apple Configurator (as hinted by @notytony here) or simply in the console under Window -> Devices and simulators -> Open Console
, then choose the device (previously attached via USB cable). Like so I could catch the error message:
does not pass CT evaluation; Unrecoverable CT signature issue
which pointed me to this answer, which suggests to go over several certificates (most notably "Apple Worldwide Developer Relations Certification Authority") making sure the trust level is set to "Use System Defaults". Still I couldn't launch on device, but the previous message was no longer present in the logs. No other meaningful error was shown.
I was stuck here. Nothing listed here worked: rebooting device, revoking certificates and provisioning profiles and recreating new ones, clean build, restart Xcode, signing out and in again from AppleID,... the only workaround at this point (and only after fixing the trust issue from the certificates) was to uncheck the "debug executable" in the project scheme, which is not ideal.
I then tested on another device and it worked, even with "debug executable" enabled. After that, launching on the original device worked again as well. Something must have been reset on that AppleId account that it can successfully sign and provision apps again on the original device.