As you note, the "consent" objection to bestiality is unconvincing, and not only because animals presumably do not consent to being eaten, but also because "consent" is a legal term that has no objective relevance. In legalese, "consent" is not the same as "willingness". In many jurisdictions, there is an age of consent such that someone below that age can be willing to have sex, but they can't consent to have sex. Obviously nothing magical happens on a person's 18th birthday; they don't magically acquire knew powers of judgment, so this is an arbitrary division put there for legal reasons (when I say "arbitrary" I don't mean that there is no justification for laws about consent; I mean that the dividing line is arbitrary).
As far as I know, even the legal definition doesn't apply to animals, so the notion of a distinction between consent and willingness doesn't even apply in bestiality, and there are certainly cases where animals are willing to engage in sexual activities with humans.
There are other moral arguments for why bestiality is wrong, but those arguments inevitably lead to other things being wrong that people don't want to think are wrong. One argument has to do with proper function and disordered desires. The argument goes like this: our bodies are designed to function in a certain way, and our parts have specific purposes. The digestive/elimination system, for example is designed to nourish the body, but eating is pleasurable even when it is not nourishing, so some people are prone to a disordered desire to eat more than they need. It is morally wrong to give in to this disordered desire.
This position leads to the conclusion that it is wrong to eat more than you need, and it is especially wrong to eat and purge, which abuses both the eating and the elimination functions of your body. Smoking would also be morally wrong because it abuses the function of your lungs.
Sex would be just another example of a bodily function with a specific purpose. Sex has the purpose of propagating the species and of creating male/female emotional bonds (to keep the male around to help the female support the children). This would imply that any sex other than than vaginal intercourse between a bonded male/female pair is immoral. In particular, masturbation and sodomy would be wrong.
Now, the words "function" and "purpose" don't have any moral implications on their own. The function of a claw hammer is to pound and pull nails, but that doesn't mean it would be immoral to use the claw hammer to break through a wall. Similarly, the function of the sex organs is to reproduce, but that does not mean that it would be immoral to use them for other purposes. Therefore, we need an additional premise or an additional argument to move from function or purpose to moral obligations.
One thing we could do is to have a simple moral axiom (a premise that is just known to be true and is not the conclusion of an argument). If you believe that moral truth is objective and real (as opposed to subjective or reducible to another form of truth), then you have to admit the existence of moral axioms. That is, there are moral truths that are just true; they can't be explained or justified on other grounds.
Most people do believe in moral axioms at some level, although they acknowledge different axioms. Some people believe there is an axiomatic moral obligation to support family members. Others believe that there is an axiomatic moral obligation not to torture people. Others believe that there is an axiomatic moral obligation not to indulge disordered appetites.
If you don't accept that last moral axiom, there are other arguments to justify the prohibition on disordered appetites. These arguments must appeal to some more fundamental moral principle. One example would be an appeal to God's will. The idea is that God designed the human body to function in a certain way, and that we have an obligation to follow God's will.
Another example would be an appeal to the moral axiom that we have an obligation to live our best possible life. Indulging in disordered appetites will have consequences, some we can predict and some that we cannot. These consequences may be physical, emotional, social, or something else, and although we can't be certain the consequences are all bad, we can reasonably assume that doing things that are unnatural will lead to consequences that are against our nature. Indulging these passions, then, is an immorally reckless behavior.