I can't enter Command+Shift+Up/Down on macOS Sierra Since upgrading to macOS Sierra (10.12.1 non-beta), I can no longer enter the keyboard combination Command+Shift+Up Arrow or Command+Shift+Down Arrow. I use this in text editors to select everything above or below my text cursor. On the macOS Keyboard Viewer, when I press the combination, only the Command and Shift keys show as pressed down.Command+Shift+Left/Right Arrow works just fine though.

I'm not sure what's going on. I haven't found anyone else with this problem on Sierra. I used to have Karabiner installed, but uninstalled it after finding it wasn't compatible with Sierra. I also had Karabiner Elements installed for a bit, but uninstalled it as well. Restarting doesn't do anything to change the problem. The problem occurs on both my MacBook Pro keyboard and my external keyboard.
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.