I meant Rds(on) @ Vgs. From that datasheet:
RDS(on) Static Drain-Source On-Resistance VGS = -10 V, ID = -3.5 A Typ. 0.32 Max. 0.41 ?
So it's not suitable, Vgs(on) isn't quoted at 5v or lower. Try http://uk.farnell.com/international-rectifier/irlib9343pbf/mosfet-p-to-220-isol/dp/9933867. If you go to the datasheet you will find that it has Rds(on) quoted at Vgs = 4.5v as well as 10v.
Just for my basic understanding of reading a Mosfet's datasheet:
Rds(on) is the Resistance between Drain and Source when i connect the given "@" voltage.
Now according to Figure 12 of http://www.irf.com/product-info/datasheets/data/irlib9343pbf.pdf i know where i made the mistake:
I always thought the Mosfet becomes conductive when i have the right voltage difference between source and gate. But obviously things are not that easy 
The problem is that the resistance gets very high when the Voltage difference between source and drain is too low! lightbulb So Vds(on) significantly influences the resistance of the Mosfet.
Are there more tripping hazards like this?
No, that's not quite right, it's not the drain voltage Vds that affects the resistance, it's the gate voltage (Vgs) and the drain current (Ids).
When the gate-source voltage (Vgs) exceeds the gate threshold voltage, the mosfet starts to conduct. However, the resistance between source and drain will only be low up to a certain current. That current depends on the Vgs, the gate-source voltage. A higher Vgs keeps the resistance low up to a higher current. You can see this effect in fig. 1 and fig. 2 of the data sheet for the IRLIB9343PBF, the curves flatten off on the right hand side.
The actual limiting current for a given Vgs can vary quite a lot for a given type of mosfet. However, the manufacturer tests the Rds(on) at one or more combinations of Vgs and drain current (Ids), as shown on the data sheet. So you need to pick a mosfet where the quoted Rds(on) is low enough, at a test current at least as high as the current you want to switch, and at a Vgs that is no higher than the Arduino can provide (i.e. 5v).
So just to learn something...
this one fits too: http://www.irf.com/product-info/datasheets/data/irlz24pbf.pdf
It is npn so the values of the pwm will react the other way round...
Yes, that's specified at Vgs = 4v and 5v, so it's suitable for driving from an Arduino pin (a resistor between the pin and the mosfet gate of 100 to 150 ohms is recommended when driving power mosfets).
btw bipolar transistors are npn or pnp, but mosfets are p-channel or n-channel. An n-channel mosfet is connected it in the ground side of the load you are switching, rather then the +5v side. I wouldn't recommend driving an n-channel mosfet from a tlc5940 because reversing the pwm changes the range from from 0 - 4095 to 1 - 4096 so you can't turn the led off completely (or so I have heard, and it sounds entirely plausible).