I decided to do a little digging into the release history of KFX. I know that the Kindle iOS app has supported it since version 4.9 (May 2015) and recent e-ink Kindles support it as of version 5.6.5 (August 2015).
I was wondering when support was added to Fire devices so I did a little snooping. By checking downloadable firmware updates for strings related to KFX I was able to see that support was first added in the 4th quarter of 2013 with the release of the 3rd Generation Fire devices. This is much earlier than I expected!
It seems that the roll out of KFX has been going on for a lot longer and at a much slower pace than I thought.
----Edit----
Here is a bit more information on my method:
Since Amazon usually only lists
the most recent version of each device's firmware on their website, I searched in Google for older firmware versions. I was able to find quite a few. (I wouldn't recommend actually installing anything found that way; too much chance of tampering.)
The Fire firmware files are archives in zip format. I expanded them and then searched for strings associated with the KFX format, such as 'yj' and 'kfx'. After weeding through many false positives I was able to come up with longer strings that work better, including 'yjsdk' and 'parseKFXContainer'. I found that when these strings occur they are most often in the file named '/lib/libKRF.so'.
Since the file dates within the archives are unreliable (most are 9/6/2011), I used the 'post-timestamp' (in Unix format) found in /META-INF/com/android/metadata to determine when each release was actually created.
I wasn't able to find every release, but I found enough to narrow the window of when KFX first appeared to late 2013. The earliest release I found with KFX support was Kindle Fire HDX 8.9 (3rd Generation) OS version 3.0.5, dated 10/29/2013. The second generation Fires also received an update with KFX around the same time.