Permission hierarchy vs. WITH GRANT OPTION
Unfortunately the WITH GRANT permission is not inherited in some, or perhaps all, cases.  I couldn't find anything in the documentation or other articles on the [cue thunder] World Wide Web [stop thunder] stating that, though.  I am with you in that I would expect it to be inherited.

I tested this on SQL Server 2016 and got the same results as you did.  There are several options to work around it, but the most fine-grained option would be to assign EXECUTE WITH GRANT to SchemaUpdater on each stored procedure.

GRANT EXECUTE ON [dbo].[sp_MyProc] TO [SchemaUpdater] WITH GRANT OPTION


I have confirmed that WITH GRANT is not inherited on other permissions and objects as well.  I tested the same scenario with VIEW DEFINITION on a table, and had to explicitly GRANT WITH GRANT on the table before SchemaUpdater could grant that permission to another user.

So the specific answers to your questions: 


Since WITH GRANT is not inherited, a user must have explicit WITH GRANT permission on an object in order to grant permissions.  Since SchemaUpdater has EXECUTE WITH GRANT on the database, it can grant EXECUTE on the database.  Since it doesn't have an explicit EXECUTE WITH GRANT on the stored procedure, it cannot grant explicit permissions on that stored procedure.  
As mentioned, SchemaUpdater will need EXECUTE WITH GRANT explicitly on each stored procedure, or a higher privilege that includes that permission (such as db_owner).