You guys bring up several interesting points that have brought up further questions:
1) Why exactly are the plant companions not qualified for the Plant Shape spell? I don't understand what stats are missing that would be required by the Plant Shape spell. Plant Shape says "you can assume the form of any Small or Medium creature of the plant type" and the plant companions listed under Treesinger are described as "a creature of the plant type".
2) There are a number of plants that can fly that are listed in the bestiary database. Is this not a valid place to look for options available to Plant Shape? What indicators should I be looking for to identify the legal options from others?
3) What does Plant Shape have to do with Beast Shape? I don't see anything stating a connection between the two or a reference from one to the other.
4) It is pretty clear that the Fly skill does not grant the ability to fly, only that one is skilled at flying. It also seems well "understood" that one cannot fly without a fly speed. But I still don't understand where that consensus comes from. Is it not possible to receive the ability to fly without also having a fly speed? Is this impossibility something that is implied simply because there isn't any known instance where something grants the ability to fly but doesn't also give a fly speed?