Does the force of kinetic friction increase with the relative speed of the objects involved? If not, why not?

At the simple level of approximation where you talk about kinetic friction, it doesn't depend on speed. It's not a great approximation (the coefficients of kinetic friction that you find for materials tend to have huge uncertainties), though.

The reason we use the approximation (other than that it makes for good intro mechanics problems) is that the microscopic physics is pretty complicated. At a very small scale, all objects are somewhat rough (at the atomic scale, if not before), and friction is the result of trying to drag one corrugated surface over another. Larger projections from the surfaces will snag against each other and require some force to dislodge, and the sum of all those microscopic snags and drags is the force we see as friction. As it's impossible to keep track of all those interactions in detail for any reasonable size object, we approximate the total force using the kinetic friction model.

Kinetic friction has nothing to do with the airplane-on-a-treadmill problem, though. Kinetic friction involves two surfaces sliding across one another. In a situation involving rolling, however, there is no sliding. At the point where the wheels of the airplane come in contact with the surface of the ground (or a treadmill), the wheel surface is not moving relative to the ground. The relative speed of the bit of the wheel touching the ground and the bit of ground that it is touching is always zero, no matter how fast the wheel is moving relative to the surface.

A cute way to see this is to place a ruler on top of a couple of soda cans (or other convenient round objects), and roll it some distance along the surface of a table next to another ruler. You'll find that the distance covered by the ruler on top of the cans is double that covered by the center of one of the cans. This happens because the point where the cans touch the table is stationary relative to the table. The centers of the cans move, though, which means that the top part of the rolling can must be moving at twice the speed of the center for the average speed of the can to work out. You can think of the contact point, center, and top being (at some instant) like points connected by a stick that pivots about the contact point-- the point at the far end of the stick will move twice as fast as the point at the halfway mark (obviously, this only holds exactly for the infinitesimal amout of time between when a given bit of can hits the table and when it lifts off again as the roll continues, but it gets you the right idea). Thus, the ruler along the top moves twice as far as the center of the cans.