Arduino alternate PWM input method
the pulseIn is a blocking command that waits for it to complete, plus its overhead. Sounds like you should directly set up and us the Input Capture Interrupts. They capture the exact time of the edge, creating an interrupt. And some time (soon) after the Service of the interrupt reads the latch time. See example InputCapture.ino. From this example you can scale it capture all the inputs, assuming you have enough Input Capture Pins.

If you don't need exact (nano second) then you can use PinChangeInt to get an interrupt and at time of Interrupt service record the time stamp. A bit latent, but may have the precision you require.