But isn’t the embedded element already setting cookies before the user can reject the cookie notice?
The GDPR absolutely requires opt-in before setting cookies (or collecting user data in other ways, it isn't specific to cookies even) so the embeds would be in breach. Whether it's the responsibility of the parent website or the embedded element to ask for consent is another matter.