OK I found out the solution to this. In order for Embedded Coder to show up in the Simulink Apps menu, you need to install Simulink Coder Add On. This is not mentioned in Embedded Coder pre-requisites and apparently Matlab staff thinks that Embedded Coder does not show up as an app, but that's not true (see screenshot attached).
I hope this helps others save from the frustration I had to face.