This is a sticky wicket. As written, gargoyles are elementals...elementals, by definition [and ironically], are not creatures of the natural physical world. They are/come from a different realm of reality...and so, could be conceived of as "Magical"...like ye olde category of monster called "Magical Beast."
But this is not RAW.
Certain abilities, such as Detect Good/Evil (spell) would/should by defintion *ping* an elemental...visible, invisible, behind a door or hiding within range.
Detect Magic, by definition, reveals "creatures or objects which bear magic"...So the question becomes, in their [super-/preter-]natural state, do gargoyles "bear magic"?
If the gargoyles were not under the effects of some spell (such as hidden by an illusion), spell-like ability -which their False Appearance ability might or might not be defined as, according to the DM, and/or in possession of some magic item...in which case the ITEM would *ping* for detect magic...or are, themselves, in the process of working some magic, then I am left with little option but to say, No. They would not show up on a Detect Magic sweep.
I, personally, give my gargoyles the ability to appear as/shapeshift into any humanoid statue...so the players, upon hearing there is a statue with wings and horns and a bestial visage do not automatically attack it..."cuz, duuuh, gargoyle!" But this is a "natural" ability of the gargoyle, in my games, and so they have, literally, a False Appearance. Works quite well and so, given what's written in the 5e MM, I see no reason to alter it.
My verdict is your ruling is not inappropriate.
But it is also not...summarily...correct in all cases/at all tables, either. I can see/understand your Warlock's objection.
Bottom line, though, you're the DM. Gargoyles are an elemental monster, as written. Detect Magic, as written, does not reveal elementals. What you say goes.
IF elementals are considered beings "of [that bear] magic" that is something for you to define in world...and you have elected not to. So, the appropriate thing here is for the Warlock PC to say, in character, "Huh. I always thought elementals were magical creatures. Seems not. Note to self for future reference: Do some studying up on/ask my Patron about elemental creatures."