I thought it was obvious from my answer:
Independent of New Guinea masks: as soon as humans started representing things beautifully or abstractly, when they might have done without that extra effort, they started doing art. They were investing unneeded energy in something that didn't give them a tangible benefit, only a satisfaction.
The first tattoos might have been striking and given a "mating" advantage (but why did the first one come up?), but when everyone started tattooing that advantage was diluted, and they kept doing it because of something else. Call it "culture", but culture is the set of things we do that differentiate us from other groups. If they were compulsory for survival they would be common, so culture is the set of things that we choose to do one way without an imperative reason, i.e. because we somehow like them, by themselves and for themselves. Sometimes technical, sometimes religious, sometimes political, sometimes artistical.
Now, I'll give you that a tattoo or a mask in a tribal society may acquire an additional "meaning". But when someone, alone, expends their time in doing something beautiful, it is for their own enjoyment. A shepherd playing a flute in the middle of nowhere is not earning a "competitive advantage", so it is not utilitarian, it is for the feeling of beauty, for some need to "contribute" to the beauty (or to dilute the ugliness) of their environment. Is not that art?
When a mom sings a lullaby to her kids, she could as well talk softly, or simply hum a monotonous note and get the same result. So, when she sings, what is the "utilitarian" (or "religious" or whatever) reason? Isn't this just art?
And when a priest or prayer offers something to the gods, they can just throw in the animal fat (the most savory part) to the fire (like Achilles in the Illiad) or they can expend time carving a mask. Why do they think that carving a mask may be more pleasant to the gods than giving them the best food? They can only think so if they find the carving more appealing to themselves, if they feel that a beautifully carved wooden good (like the mask) is more satisfactory than a plain one. That is, they first feel satisfied by the beauty and then they offer what they find most agreeable to their gods.
Actually, they create and appreciate art, and when they find it beautiful and satisfactory, and because they do, and only then, do they offer it to their gods. So, art was there first, and then it became an offer.
A hunter who expends waiting hours carving the handles of his tools (or painting them, or knitting ropes) is not utilitarian, actually it may make handling them less practical, but they will be more beautiful and that satisfies some internal need. Is not art this?
Ultimately, we may claim all art is not. If we look at evolution, we may conclude it is all utilitarian, maybe "corrupted" utilitarian: tattoos, skin paints, garment decorations, ... can be likened to the mating "plumage" of birds, carving and dancing abilities may be a show off of psycho-technical proficiency and coordination that proclaims our qualities and makes us more desirable to mates, friends, rulers... like the kid jumping "choose me" when making teams to play, whatever.
But in that case, that "corrupted" utilitarianism (that we have been selected to feel well about doing/observing harmonious and beautiful things, beyond an immediate benefit, as an underpainting of (or a continued training in) our life, because overall, in the long term it may pose an evolutionary benefit) is what we call art anyways.
So, no matter how you define it, art was first.