What does existential unforgeability mean in a digital signature scheme?
"Existential unforgeability" alone means adversaries can't create signatures that verify for messages they have not already a signature for. Strictly speaking, breaking existential unforgeability may only mean adversaries end up with a message and signature that verify, but the message is gibberish void of any use for the adversaries.
There is also "strong existential unforgeability", which additionally means adversaries can't create new signatures that verify, against any message. ECDSA is an example of scheme with existential unforgeability, but not strong existential unforgeability. That's because if $(r,s)$ is a valid signature for some message, then the different $(r,n-s)$ also is valid for the same message.
The "existential" adjective opposes to the more difficult goal for adversaries of signing a message they choose, in whole ("selective forgery") or part (e.g. choosing a prefix of the document), to have a meaning useful for some nefarious goal against the system using digital signature. "Existential" refers to the fact "there exists" a (message, signature) pair with new message (or/and new signature) that pass verification in what the adversaries produce.
"Existential unforgeability" is often followed by "under chosen message attack", meaning adversaries are assumed to be able to obtain signatures for messages of their choice. The messages they submit for signature are discounted from those that count as successful forgery. In strong existential forgery, the signatures they obtain this way are similarly discounted. Chosen message attack opposes to known (message, signature) pair(s), and no-message attack.
It's common that an existential forgery can be extended to meaningful messages or exploited in some devious way (like a buffer overflow, denial of service or code injection). It's also common that adversaries can influence enough the messages that get signed to make an attack possible even though it does not qualify as a full-fledged chosen message attack. There's also the danger of adversaries merely pretending other adversaries have ruined the security, breaking trust in the system. Therefore, it has become the baseline to require Existential UnForgeability under chosen message attack (EUF-CMA). This adequately protects against message alteration without approval of the holder of a public key.
I refer to this answer for a more formal taxonomy of UF variants.
Best practice for modern signature schemes is strong EUF-CMA, plus Signature Collision Resistance, and Universal Exclusive Ownership. See Dennis Jackson, Cas Cremers, Katriel Cohn-Gordon and Ralf Sasse: Seems Legit: Automated Analysis of Subtle Attacks on Protocols that Use Signatures, in Cryptology ePrint Archive, Report 2019/779, originally in proceedings of ACM CCS 2019.
In a digital signature scheme (Gen, Sign, Verfiy) that satisfies correctness and existential unforgeability, can you assume that the outputs of Sign() are computationally indistinguishable from random?
No. For example RSASSA-PSS is provably sEUF-CMA, yet it's signatures are distinguishable from random (by examining the high-order bit of the first byte of the undecorated signature, which is biased towards 0 unless the public key has many high-order bits at 1, or/and something in the signature procedure is crafted to make such bias less detectable; which is easy, but uncommon). That's even without the public key or message. Obviously, if the public key and message is known, no correct signature scheme can have it's signature indistinguishable from random; the verifier is a distinguisher!