Fast asleep is an idiom meaning deeply asleep. To say someone is fast asleep is to say that they are so deeply asleep that it is not easy to disturb them.
The word fast within the idiom fast asleep does not refer to speed. Instead it has a meaning similar to firmly, strongly, tight, or secure. If you said, "He is firmly asleep," it would mean the same thing as "he is fast asleep". This meaning of the word fast is also seen elsewhere in the English language, such as a sailor making a boat fast to the dock meaning they are tying the boat firmly to the dock, or when a jar lid is stuck fast, meaning the jar lid is too tightly stuck and is almost impossible to open. One can also hold fast to one's ideals, meaning to be firm and keep one's ideals secure as they are.
To say someone fell fast asleep is to imply they went from awake to deeply asleep quickly. The same meaning could be implied from saying someone fell deeply asleep or fell firmly asleep. The speed is not inferred from the word fast meaning quick, but rather from the qualifier of the deep quality of sleep being added to fell asleep.
Now, an excellent terrible pun from the movie Hook, making use of the two different meanings of the word fast. As Smee says, Captain Hook is "A man so quick, he's even fast asleep."