If an illustration of a dubious event counts as fiction, then this late 1500s sketch could be the first reference to familiars:
The author is unknown, but there is a description here:
An image of a witch and her familiar spirits taken from a publication that dealt with the witch trials of Elizabeth Stile, Mother Dutten, Mother Devell and Mother Margaret in Windsor, 1579.
Whether the term "familiar" would have been used by the author at the time is unclear. However, the sketch was made some time after 1579 and in 1584 we find what is likely the first appearance of the term "familiars" in this context within the English corpus. This appears in the book Scot's Discovery of Witchcraft, edited by Reginald Scot. (This could be earlier than Malleus Maleficarum.)
The term appears in the very long subtitle of the book:
Proving the Common Opinions of Witches Contracting with Divels, Spirits, Or Familiars, and Their Power to Kill, Torment, and Consume the Bodies of Men, Women, and Children, Or Other Creatures by Diseases Or Otherwise, Their Flying in the Air...
This is less than half of the subtitle, by the way.
This reference, however, is not a work of fiction (at least, it wasn't intended to be a work of fiction — beliefs were a little different back then).
I believe we should refer to the French corpus for the first clear appearance in fiction. The first usage seems to be in the 1857 poetry collection Les fleurs du mal (The Flowers of Evil) by Charles Baudelaire.
The French poet Charles Baudelaire, a cat fancier, believed in familiar spirits:
It is the familiar spirit of the place;
It judges, presides, inspires Everything in its empire; It is perhaps a fairy or a god? When my eyes, drawn like a magnet To this cat that I love...
(Source, in English)
There are of course earlier instances of the concept in both languages, in folklore and tales, etc. However, I have focused on the appearance of the actual term, as requested by the OP.