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.
Put it on the arxiv. Yes, it is not refereed, but it does give you some limited visibility, and sooner or later, if it is interesting, it would get cited.
IPL (for Information Processing Letters) is a good place for publishing short papers.