I tested shortcuts in the Notes app, and it was not working.
So I went to Settings > General > Keyboards > Shortcuts and played around a bit: deleted a couple of older shortcuts that had reappear and created a new one.
When I went back to the Notes app shortcuts were working again.
Since you said a reboot did not work, I decided to do a reboot and check again. Sure enough the shortcuts stopped working. After some more experimenting I narrowed it down to having to actually create or edit a shortcut in settings before the feature starts working again.
Annoying.
I've sent feedback to Apple. Pretty close to exactly what I wrote here. Won't hurt for you to do the same if you want to bump the issue a bit higher on thier to-do list.