Create unique constraint with null columns

You could create a unique index with a coalesce on the MenuId:

CREATE UNIQUE INDEX
Favorites_UniqueFavorite ON Favorites
(UserId, COALESCE(MenuId, '00000000-0000-0000-0000-000000000000'), RecipeId);

You'd just need to pick a UUID for the COALESCE that will never occur in "real life". You'd probably never see a zero UUID in real life but you could add a CHECK constraint if you are paranoid (and since they really are out to get you...):

alter table Favorites
add constraint check
(MenuId <> '00000000-0000-0000-0000-000000000000')

Postgres 15 or newer

Postgres 15 (currently beta) adds the clause NULLS NOT DISTINCT. The release notes:

• Allow unique constraints and indexes to treat NULL values as not distinct (Peter Eisentraut)

  Previously NULL values were always indexed as distinct values, but this can now be changed by creating constraints and indexes using UNIQUE NULLS NOT DISTINCT.

With this clause NULL is treated like just another value, and a UNIQUE constraint does not allow more than one row with the same NULL value. The task is simple now:

ALTER TABLE favorites
ADD CONSTRAINT favo_uni UNIQUE NULLS NOT DISTINCT (user_id, menu_id, recipe_id);

There are examples in the manual chapter "Unique Constraints".
The clause switches behavior for all index keys. You can't treat NULL as equal for one key, but not for another.
NULLS DISTINCT remains the default (in line with standard SQL) and does not have to be spelled out.

The same clause works for a UNIQUE index, too:

CREATE UNIQUE INDEX favo_uni_idx
ON favorites (user_id, menu_id, recipe_id) NULLS NOT DISTINCT;

Note the position of the new clause after the key fields.

Postgres 14 or older

Create two partial indexes:

CREATE UNIQUE INDEX favo_3col_uni_idx ON favorites (user_id, menu_id, recipe_id)
WHERE menu_id IS NOT NULL;

CREATE UNIQUE INDEX favo_2col_uni_idx ON favorites (user_id, recipe_id)
WHERE menu_id IS NULL;

This way, there can only be one combination of (user_id, recipe_id) where menu_id IS NULL, effectively implementing the desired constraint.

Possible drawbacks:

• You cannot have a foreign key referencing (user_id, menu_id, recipe_id). (It seems unlikely you'd want a FK reference three columns wide - use the PK column instead!)
• You cannot base CLUSTER on a partial index.
• Queries without a matching WHERE condition cannot use the partial index.

If you need a complete index, you can alternatively drop the WHERE condition from favo_3col_uni_idx and your requirements are still enforced.
The index, now comprising the whole table, overlaps with the other one and gets bigger. Depending on typical queries and the percentage of NULL values, this may or may not be useful. In extreme situations it may even help to maintain all three indexes (the two partial ones and a total on top).

This is a good solution for a single nullable column, maybe for two. But it gets out of hands quickly for more as you need a separate partial index for every combination of nullable columns, so the number grows binomially. For multiple nullable columns, see instead:

• Why doesn't my UNIQUE constraint trigger?

Aside: I advise not to use mixed case identifiers in PostgreSQL.

You can store favourites with no associated menu in a separate table:

CREATE TABLE FavoriteWithoutMenu
(
  FavoriteWithoutMenuId uuid NOT NULL, --Primary key
  UserId uuid NOT NULL,
  RecipeId uuid NOT NULL,
  UNIQUE KEY (UserId, RecipeId)
)