Learn Portuguese (Portugal): A mascote esteve no labirinto comigo.

Both translate to "was", but they frame the past differently. Using esteve treats the time spent in the maze as a single, completed event that is now over. If you used estava, it would set a scene or describe an ongoing background state, leaving the listener waiting for another action to interrupt (like "The mascot was in the maze when the lights went out").

Since this lesson is about verbs changing meaning with a reflexive pronoun, can we use estar-se here?

No, you cannot say esteve-se no labirinto. Unlike verbs that gain a completely new meaning when made reflexive, estar is essentially a state verb and does not take a reflexive pronoun for location. The only time you'll see estar used reflexively is in fixed idioms, such as the informal Portuguese expression estar-se nas tintas (to not care at all).

Is the word mascote always feminine, even if the mascot is a male character?

Yes, mascote is what we call an epicene noun. It is permanently feminine (a mascote), so any adjectives or articles attached to it must also be feminine, regardless of the actual gender of the person or animal inside the costume.