According to Bulbapedia:
Certain Pokemon without visible mouths, such as Metapod and Cascoon, cannot eat PokePuffs
I think the key word is certain. For whatever reason, GameFreak has decided that some Pokemon without mouths should not be able eat PokePuffs, while other Pokemon with mouths should be able to. I'm not surprised; after all, Ghastly can learn the elemental punches.
After digging around on some forums, I found some people who said that they couldn't feed other cocoon Pokemon like Kakuna and Spewpa. So maybe all second-stage Bug type cocoon Pokemon cannot eat PokePuffs. Pokemon that fit into this category are:
Metapod, Kakuna, Silcoon, Cascoon, Swadloon, Spewpa, and possibly Whirlipede (sadly, I don't have a DS to test this theory)
However, Shedninja also doesn't eat PokePuffs, and it really doesn't fit in with the Pokemon above because it doesn't have a three-stage evolution line. So the second-stage Bug type theory most likely isn't correct.
Sep suggested another plausible theory:
It might not be because they don't have mouths, but instead because they are all in shells. All of the Pokemon that cannot eat PokePuffs are Bug type Pokemon in a cocoon, as their mouth is covered by the cocoon.
If anyone wants to test this, please do. I would like to figure this out but I do not have a DS.
Strangely enough, none of the major Pokemon websites like Bulbapedia or Serebii had any lists of Pokemon who couldn't eat PokePuffs. In fact, most of them didn't even address this fact at all, which is why I've been trying to figure out what the pattern is. So I couldn't find a list for you.
To answer your second question... you can't increase their fullness. You can only increase their affection by petting and playing with them.