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), you cannot base CLUSTER on a partial index, and queries without a matching WHERE condition cannot use the partial index. (It seems unlikely you'd want a FK reference three columns wide - use the PK column instead).
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 might even help to maintain all three indexes (the two partial ones and a total on top).
Aside: I advise not to use mixed case identifiers in PostgreSQL.