I am asking in the context of “pets” as animals optionally kept exclusively for “companionship” and not for a utilitarian purpose such as a food supply, weapon, religious purposes, etc.
We don’t know. But you’re in luck. PBS’s *Nature *show (on 8PM EDT and PDT) has a two part series on the origin of the dog, starting tonight.
It’s thought that the dog was the first animal domesticated, but we don’t know when. I’ve seen 15k years ago, and I’ve seen 100k years ago.
As for adopting wild animals as pets (and not necessarily domesticating them), that might go back further. But we don’t know.
Cypriots and cats, 9500 years ago?: http://www.chinadaily.com.cn/life/2009-11/03/content_8904093.htm
Some dozen or two millennia ago, Gronk kept some sort of animal around for utilitarian reasons. Then one day, Gronk’s animal had a really, really cute puppy or kitten or whatever and his son or daughter begged Daddy to let them bring it inside . . . with the understanding that it would be he or she, and not Gronk, who would feed the animal and pick up after it.
Or maybe not. Anyway, people probably kept certain kinds of animals around for all kinds of practical reasons, ranging from protection to food to rodent control, and after a while just started feeling affection for some of them. I would guess we’ve had “pets” for just about as long as we’ve been living with non-human animals.
Also, the show John Mace refers to above is extremely interesting. I can’t wait to see Part Two.
I would think to any kind ancient person it’d be obvious that cat or cat-like animals would keep mice and rats away. So it’d be just a step from there to pets. As dogs, who would warn of possible intruders.
That ‘exclusively’ makes it real hard to give an answer here. My cats are mainly companion animals, and have me well trained to provide food & care for them. But they still catch a mouse occasionally. So they would be excluded by your definition. Most living cats on farms & in other countries probably work for their keep, even now.
Cats were used for rodent control, dogs for various uses (herding, hunting, guarding, etc.). I suppose some rich people (Pharaohs, Roman Emperors) kept individual cats or dogs strictly as a pet, but the majority of the species was still a working animal.
Gronk ended up sending that baby animal to a cave in the country because it kept chewing up the sitting logs.
But surely you don’t keep them for their mouse catching?
Gronkling: What happened to the baby goats?
Gronk: I traded the baby goats to Tonga for some sea shells for your mother.
Gronkling: EVEN SPOTTIE?
Gronk: Who’s Spottie? What kind of person would be named Spottie?
Gronkling: The little goat with the spot on his head!
Gronk: … You went and NAMED a GOAT?
Gronkling: He was… so… CUTE… waaaah
Gronk: sigh
It’s a trick answer of sorts but the first domesticated animal was probably yeast.
Granted, you rarely gave them names.
Yeast is not an animal.
A really, really long time ago. 
This past weekend a National Geographic program claimed that the practice of keeping pets seems universal among hunting peoples. As suggested above, it may predate humanity.
So it began with the first chimp to play with his food?
Og invent pet rock before Gronk get baby animal. Og still wait for resolution in trademark infringement suit. Og need better lawyer. Gronk spoil that kid. And Gronkling too.
As far as the kids know . . .
Gronk celebrate baby animals new life in country with fresh meat feast that night. Tasted like chicken.
Also Og big whiner. He copy pet rock from Homo Habilis
Gronk say not Gronk’s fault. Gronk not have modern refridgeration technology.
Og say WTF?! Gronk live in ice age. Whole world is fridge. Gronk big mammothshitter.
WAG here. Personal family experience. Some of my older relatives I knew as a child had a much different attitude about pets.
My uncle (born 1910) liked dogs, but only outside. He never really spent much time petting or playing with them. He’d put food out. Give it a couple pets on the head and get to work on the farm. He didn’t worry about fencing the dog in. The dog came and went as it pleased. It always hung around because it got fed. He never took a dog to a vet. I remember him splinting a neighbors dog’s leg that got hit by a car. It recovered. If a dog got sick, he’d pick up something that might help at the Farmers CoOp Feed store.
My other older relatives were the same way. Dogs and cats belonged outside.
The idea of an indoor pet that you fuss over constantly seems pretty recent. Perhaps since the 1940’s or 50’s.