When you feed your pet, and it says, "no adequate items exist", it means you don't have any food in your inventory. o_o; or pots; (yes you can feed pots to your pet too). But yeah, as
MiniAsakura said, its only useful to feed your pet if you use it to fight. Basically, pets only need food so that their stamina doesn't drain up when they are fighting.
If you want to rebirth your pet, yes you need another character card, or this case, another pet card. Usually though, rebirthing pets isn't like the way you rebirth your human/elf/giant chars. Pets still keep their skills and ranks of the skills, but rebirthing a pet into another pet, can make it have other skills. For example, you have a cat, with lightning bolt and ice bolt, rebirth it to a dog, and now it has the magic skills, lightning bolt, ice bolt, and firebolt. And yeah...I don't really recommend this either unless you want your pet to be stonger, otherwise, I just think its a waste of nx; I'd just spend it somewhere else.

Rebirths: 16; Total Level: 8xx