I've just completed a short (5 page) paper on proving a certain combinatorial game NP-Complete. This is in no way a result of huge significance, yet it's one that I believe is publishable. What venues would be good for a paper like this? The only one I'm aware of is Information Processing Letters; are there other ones like this?
Fun with Algorithms! Although it is a conference not a journal that you might looking for, among other things several NP-hardness results about (combinatorial) games are published here, including this one.
However this is a triennial conference (except for 2014, where the last conference was in 2012), so if you want to publish it soon then there might be a better choice.
IPL (for Information Processing Letters) is a good place for publishing short papers.