My company pays for the Gym but it is listed as "Gym Taxable" in my paycheck. Where do I report this in the 1040NR?

It should be included in your wages, which is reported on Line #7.

I reported it as "other income" on Line 21, and wrote "gym taxable". Was that OK?

That will cover it.