What is the frame window to get the menu to pop up before a trainer sees you?

I think that's 17 frames after the up input for the last step is taken into account. (maybe 16, I'm not sure) You have to press Start during that last step to have the menu pop up. As far as I know, the trainer will immediately spot you once you're completely on the tile in front of him.