If you want to send a transaction you have to do some proof of work.
Are all IoT devices (e.g. small sensors) really capable of doing the proof of work?
Will there ever be a necessity of services that do the POW for you in exchange for small fees?
Of course not all IoT devices can do proof of work.
First of all, all IoT devices is a huge variation of devices. For that generalization this question can simply be answered with a no. Especially regarding IoT sensors which usually only comprise of a sensor part and a transmitting part and no processing part worth mentioning at all. Those devices simply cannot perform any complex algorithm and they are not supposed to. When you use a million or tens of millions of them even the $1 solution from the other answer is ridiculously overpriced if the requirement is to read a value and send it somewhere.
Secondly, consider battery power. Calculating anything costs electrical power. As long as your edge device is battery powered that's a major consideration and more importantly just physics. Any proof of work is by definition (and it's also in the word) work. Work consumes electrical power. It consumes astronomical amounts of power compared to read something and send something. Thus, for any battery powered IoT sensor proof of work on the sensor will never be an option.
PoW can be quite heavy on the resources of IoT devices, But I believe that we can expect dedicated cheap IC's (chips) in the future to counter that. If you run multiple small devices a "hub" for those devices can be an option as well to do the PoW for those small devices while that hub communicates with the IoT devices over another protocol or Flash channel.
Outsourcing PoW could be an option but I think it won't be an issue in a couple of years due to the development of these IC's.
JINN is planned to be a $1 (or otherwise extremely affordable) chip designed for taking care of PoW -- keeping in mind that PoW doesn't become more difficult over time, JINN should theoretically be all that is needed for PoW. If a sensor is so small that it somehow has a radio transmitter or internet connection but not a JINN processor, it would be capable of outsourcing PoW within it's local area network, so it's not necessarily a necessity so much as a potential option / feature.
No matter what happens, there will be both, devices that run POW by themselves and devices, which can't do it.
Even if cheap processors are available, it may not be worth to compute the POW directly on the device. Energy consumption on small sensors is a valid concern for POW to be not worth it. Adding on to this, sensors may not be able to validate if their transactions actually got confirmed, or need to be reattached/promoted.
If there would be fees, they would be extremely low, due to unlimited competition. In blockchain like bitcoin, we have a "the winner takes it all" scheme, whoever finds the block gets the fees. In IOTA, anyone can do it for you. Even someone who just connected one of these processors to the internet. I could even imagine that you could run this on idle computers as a background process.
Also, you could set up a light node for your devices to connect to if you have multiple, thus outsourcing the POW just from your devices. In other words, sensors connecting to a base station which then does the work.
I think the latter is most likely to happen, as its still decentralised but more efficient.