Would the availability of legal options hinge on whether the fish are considered to be property or not? IIRC not all pets are deemed to be property, or at least under common law they weren’t. I do know that the California Penal Code, at least as of 1931, specifically states that dogs are property, seeming to imply that cats or koi aren’t. I don’t know if that section is still in place, but we do have the same PC that was instituted in 1872, with additions and revisions.
Other than the chicken wire suggestion, you could also try giving the fish somewhere to hide. Throw some big rocks/boulders in there, or depending on how deep it is, maybe even a plastic milk-crate or something. Another idea is to cover one end of the pond with wood or something - not only will that give them something to hide under, but they can get a bit of shade, too.
With nowhere for the fish to hide, you can’t blame the cat… since it’s as easy as hunting fish in a barrel! 
P.S. Just be glad you don’t have humongous feral iguanas (who don’t mind taking a dip) to contend with.
Around here, homeowners who have goldfish ponds also have birds of prey, neighbors’ dogs, coyotes, raccoons, and foxes to contend with. I’d suggest the chicken wire or similar options rather than sitting up 24/7 with a gun when it might not be legal to shoot in your area and/or shoot the target you’re aiming at.
Just trap them and take them to animal control. If they have tags, the owner pays a fine and boarding. If they have no tags, animal control will either adopt them out, or kill them for you.
I’m not the OP, but I’ve had similar problems in the past …
Balthisar, that’s a neat point. I hadn’t considered that giving them over to the local animal control will almost certainly get rid of them permanently, at least from around my property.
And as to tags … Unless they’re implanted, those can easily become “lost” before you drop a dime on the furry marauder. Now if AC decides to canvass the neighbors or recognizes the critter & knows who the owner is, there may be some issue when the owners ask how Fluffy managed to remove its own collar while lacking opposable thumbs and all.
I beg to differ… it’s extremely easy to chase off a cat with a rampaging dog!
As to the OP, Call your local municipality and ask them what your local laws are and what your course of action should be.
Heck, raccoons are smarter than most people I know.
As far as the OP, it varies by locale. Where I live landowners can shoot dogs that are harassing livestock, but I don’t know about cats.
Maybe try trapping them and spray them with water. Most cats hate that but it won’t really hurt them.
Yea, be careful. I once comtemplated using a pellet gun to get rid of a particularly stubborn woodpecker…one that is almost as common as sparrows around here.
I grew up in a rural area but now live just outside a large city. Never underestimate the insanit…er…extreme pro-animal-ist suburbanites can be and the insane… er… extreme pro-animalist laws and punishments they pass.
OP: do you live in an HOA or other community with internal bylaws? If so, start there. If not, move up to city/municipal rules, then county, state, and so on. The legal definitions of “property” (ie are the cats considered someone’s property? are the koi considered valuble livestock?) and the specifics of gun use and trapping animals are what you’re lookin’ for here.
Without knowing where in blazes you live, though, there’s not much more we can tell ya.
Legalities aside: as others have pointed out, cats are not the only animal that catches and eats fish. Dealing with ALL of them - by providing cover for the fish, the chicken wire idea, etc. - are gonna work far better in the long term than dealing with specific, individual cats.
Duck: woodpeckers are native songbirds and protected as such. Sparrows are invasive non-natives.
Also, be aware of the heirarchy. Suburbanites do not consider all animals to be equal.
Domesticated mammals>Undomesticated mammals>Birds>all others.
Or…shortened version - cute>not-cute.
So, if you are caught killing a snake that is trying to kill a kitten…you are safe.
However, if you kill a kitten that is trying to eat a snake - you are in big trouble.
For the OP - Killing a fish that is trying to eat a cat - you are ok.
Killing a cat that is trying to eat a fish - You are in big trouble.
Racoons are so smart that mankind could put them to work if they knew how smart racoons are. However, racoons are smart enough to get most people to think of them as animals.
I jest, but only slightly.
Cat? What cat? By the way, have you seen my garden lately? I’m using a new fertilizer and everything is coming up beautifully. Oh well, hope you find that cat of yours. 
In a thread a few years ago discussing the case of a guy who had been shooting cats that were killing endangered birds, someone linked to an article discussing the case where a human society rep said that shooting a cat is always illegal in the United States, period, because of animal cruelty laws. I thought that sounded somewhat unlikely, but I’m not a lawyer or a law-enforcement official, so I have no idea.
That only works if you catch them in the act. Otherwise it’s, “I’m in a cage for some reason, and some jerk is spraying me for no reason to add insult to injury.”
Now **this **is the kind of open-minded thinking I expect from Dopers!
You wouldn’t believe the kind of cooperation and discounts I get while waving even a **small **firearm around! “Excuse me - how much is this leaf-blower? Free? Really? Oh, you are too kind! Can you help me get it in my truck? You’re a doll!”
In truth, I love animals, obey all gun laws, but might shoot someone shooting a woodpecker! They’re protected, ya know.
Hold on… I just went to KoiStop and see that fishes are over 2 grand. Kittens are free!
New position: Fluffy goes. Quietly. SSS indeed!
There’s koi and then there’s goldfish. Koi are seriously expensive, goldfish - and yes, they can grow big - are not.
Me, I wouldn’t leave real koi in an exposed pond any more than I’d leave a laptop and a couple of iPads sitting unattended in public.
Seconding shoot, shovel and shut up. Especially the last part.
You leave your animals roam, you leave yourself open to losing them. This includes those that allow their dog to foul other peoples lawns. You want your dog, cat, etc., keep it at home.