I'm not sure that you can make a case for the phased abolition of cats from New Zealand within a utilitarian framework, even one counting animals' utility directly, without arguing that you also have to abolish any carnivore elsewhere in the world whose prey is not at the Malthusean fringe.
It's conceptually easy to add animals' utility to utilitarianism; read Peter Singer. Animals utility will be weighted by their self-awareness and capacity for pleasure and pain, but it counts positively and directly in the social welfare function. This interview of Peter Singer by Tyler Cowen is superb, though it doesn't hit this topic directly.
If the marginal increase in terror imposed by cats on their prey*, accounting for that cats may have greater self-awareness and greater capacity for pain and pleasure than do prey species, outweighs the cat's enjoyment of its own life (including all the murder) and the cat owner's enjoyment of the cat, then a Singer framework would support getting rid of cats. If pet owners get particular disutility from the forced euthanasia of their pets relative to not being allowed to get a new one, then it could be consistent with Gareth Morgan's proposed mandatory neutering and non-replacement.
But it's also consistent with other required policies. The proposal above is only optimal where prey animals would otherwise have had happier lives and deaths: trading starvation at the Malthusean fringe for death by cat might not be all that bad. But consider rabbits and mice in Britain that feed on crops and are not at the Malthusean fringe. Foxes that eat them then do harms little different from the harms imposed by cats here. And what of the terrors keas impose on helpless sheep?
Aha, you might say: rabbits and mice are not endangered, while some New Zealand native bats and birds could be. This matters in a Singer setup to the extent that people value endangered species more at the margin than they value rabbits and mice, and to the extent that any extinction may have flow-on effects elsewhere, but we also have to weigh it against cat owners' enjoyment. And given the likely rather large consumer surplus provided by cats, well, I'm not sure the case is obvious.
If you step outside of the utilitarian framework, it's perhaps easier to derive a "abolish cats but leave foxes alone" conclusion. Harry Clarke puts up a biodiversity standard, arguing that biodiversity should be sought for its own sake and regardless of whether people gain enjoyment from biodiversity. But if there's a continuum of policies that could be undertaken to encourage biodiversity, and if some are very costly, we have to draw a line somewhere about trading off biodiversity against other goods. And that puts us back into a utilitarian cost-benefit assessment even if we're adding in biodiversity as a non-preference-related constraint.
I'm not against this kind of messy pluralism; it's close enough to my own messy pluralism, where I invoke liberty side-constraints on utilitarianism rather than biodiversity side-constraints. But isn't it worth weighing up the shadow prices of the incremental gains? You have to put ridiculously high weight on the side constraint to reckon we shouldn't even consider cat owners' forgone enjoyment. And I'm not sure that there isn't a fundamental underlying anthropocentrism even to biodiversity standards where at least some of it seems to require choice among equilibria, and a lot of weight put on particular ex ante status quos. If many of New Zealand's species arrived here long after separation from Gondwanaland, and then evolved here, how far back should we go in turning back the clock? Sure, there was a stable equilibrium here before the arrival of Maori. But there would have been a stable equilibrium before the arrival of bats and buttercups too. And if the pre-human equilibrium was the 'best' one because it included some best stable set of creatures that didn't exist elsewhere, and we should invest resources in maintaining that set of creatures at the expense of other ones, why shouldn't we also invest resources in developing new creatures that do not exist elsewhere? There are lots of ways of increasing biodiversity.
* Every animal dies of something, eventually. If the cat kills an animal that otherwise would have died a painful death of Malthusean starvation, it has done no harm and may have done good. If the cat kills an animal that otherwise would have had a long and happy life because the environment is well below carrying capacity because there are too many predators, then it has done harm. If it kills an animal that otherwise would have soon been eaten by a weasel, rat, stoat or possum, then it's done no harm. See discussion of vegetarianism and eating fish in the Cowen-Singer discussion above-linked.