Is it okay to define a foreign key referencing a ‘user_id’ column from every table?
For your first question, I've managed many systems that do this. Some actually defined that Foreign Key relationship. Others had the "foreign key" field, but didn't define it in the database as key. This led to interesting quirks like data loaded outside of the application (pre-populated rows) having "updated by" fields with values that weren't users in the user table. Typically the tables had "ChangedBy" columns that stored User IDs and "ChangedOn" fields that stored a date/time for the change event.

For your second, why wouldn't it be normalized, if you set up the Foreign Key relationship back to a users table? You aren't duplicating the user information at the menu, restaurant, etc. tables, right? Just the foreign key ID field.