I can't enter Command+Shift+Up/Down on macOS Sierra
Since it works in Safe Mode (based on your comment) we know it's definitely a software issue. 

Basically, when you boot into Safe Mode your Mac will check the startup disk, only load necessary kernel extensions, and disable third-party fonts and startup options. Put simply, it won’t load third-party hardware drivers or startup programs.

It's likely (although not certain) that something to do with your prior installation of Karabiner is causing the problem. Your question didn't specify what version of Karabiner you had installed (besides the fact you also tried Karabiner Elements) or how you removed it. Assuming you've removed and deleted the application itself, there may still be other files installed. I would do the following:

Check the top level 'Library' folder of your hard disk for anything that looks like it's associated with your Karabiner installation. In particular, look at the following locations:

/Library
/Library/Caches
/Library/Preferences
/Library/Application Support
/Library/LaunchAgents
/Library/LaunchDaemons
/Library/PreferencePanes
/Library/StartupItems


If you find anything, delete the files.

Now, also do the same thing with the same set of folders within your User's Library folder. To access this, within the Finder click on the Go menu while holding the Option key and select Library.

Let us know how you go.