Ok - I renamed my /system/usr/keylayout/Vendor_0a5c_Product_8502.kl to /system/usr/keylayout/Vendor_0a5c_Product_8502.kl.old and rebooted.
Paired my keyboard and everything worked flawlessly. Since I'm from Germany I wanted to switch to a german layout. You can switch from the generic layout to the german by choosing the appropriate layout on Language and Input. Not all keys are working (like the mute button or the current apps running button) but I can finally type.
Ya, that was my post. It seems that Android, as of 4.3, is incorrectly detecting various bluetooth keyboards(all?) as "Broadcom Bluetooth Device", with keyboard type "KEYBOARD_TYPE_NON_ALPHABETIC", which is typically used for bluetooth game controllers(verified programmatically in the code for a game I'm working on).
For those looking to fix it: Renaming the file above requires root access. It's probably possible using a root file explorer, but I used a root terminal(specifically, terminal emulator logged in as root). I'll post here some instructions on how to accomplish it if you're using a terminal:
Note: first line is only needed if using a shell that doesn't automatically log into root. For example, it's unnecessary if using "adb shell" from a remote computer
Code:
su
mount -o remount,rw /system
cd /system/usr/keylayout
mv Vendor_0a5c_Product_8502.kl Vendor_0a5c_Product_8502.kl.bak
After that, reboot and you *should* be golden(I take no responsibility if this in some way breaks your device or generally doesn't work; this is just what worked for me).
I honestly haven't tried using a root explorer, but in theory that would just involve navigating to /system/usr/keylayout in said explorer and renaming the file from the GUI. Assuming, of course, that the explorer knows to remount /system as read/writable(or has a function to do so, in which case: do that first)