If animals are incapable of recognizing right and wrong in their own actions, how can they possibly do so in actions towards them?
Many objects of ethics are incapable of recognizing right and wrong. For example, if I kill somebody, that person is dead and cannot recognize anything. Unborn humans cannot recognize anything. If I hurt a fresh baby, it certainly was not yet able to recognize that act as morally wrong, even though it felt the pain in an animalistic way. Same goes for demented or otherwise brain-damaged people (hence, for example, all the fuss about when to "turn off the machines" with people in a permanent coma). Generally, the capability of the "receiver" of our actions seems not to matter so much.
How can killing a lion be evil when the lion killing another animal is not evil?
This is generally directly related to the intent behind the killing. For example, killing a lion in self-defence is not evil. Killing the animal as food is generally not considered evil (let's stay away from the vegan discussion here - assume being a native hunter-gatherer tribe which kills exactly the amount of animals they need to survive).
Killing the lion can be evil if done for fun or adventure, for profit, for gloating, etc.
Indeed, if animals are incapable of moral agency, how is killing an animal different from destroying a (complex) machine?
Firstly, ethics is concerned with values, in general, not just direct personal damage to humans. Values are subjective. Some people consider the fact that we live in a world with a complex ecology a value. Some people view it as a value to live like a guest in a very big house - where you would not go around destroying random items either.
Secondly, one can view ethics as a way to keep people from abusing their power. We all have the power to literally eradicate any animal and plant around us, and Bob knows we (as a species) are certaily doing so in many occasion. So restricting our own power to destroy - no matter the object of the destruction - certainly is a valuable part of ethics. If nothing else, the world would be very boring if everything except us was dead!
Thirdly, all mysticism and personal opinion aside, one utilitarian argument that's a relatively simple metric is to ask "if I destroy object X, can I repair or replace it (and do I really know all the results of my actions)"? For a machine, the answer is probably "yes" (if I have enough money etc. I can buy a replacement, but there may be exceptions, like a machine that runs life support for someone...); for an animal (or, say, a 500 year old rare tree, a species of flowers, etc.), the answer is "no". Thus, something being "one of a kind" is a value in itself, where it certainly behooves humans to pay attention. Funnily, in my experience, this is one surprisingly valuable argument to teach to little children (for totally everyday questions - whether to kill that bee that sits on your cone of ice, or not...).