Samples would help.
Relative search might not do much. I have even heard tales (and seen tools) for 24bit characters, though I have no reason to suspect it happening here. Not to mention the euc0jp and shiftJIS include Roman characters beyond their usual "extension/subset of unicode" approach.
http://www.rikai.com/library/kanjitables/kanji_codes.euc.shtml http://www.rikai.com/library/kanjitables/kanji_codes.sjis.shtmlAnother way is text pictures. Japanese visual novels and low text games being where I usually find examples of this.
Finding the text. What about altering the file and seeing what happens? It is well worth knowing the static analysis methods but if testing something out consists of double clicking something and seeing what happens in the game then do that. Increase a value by 1, do a random string, do a known repeating string, do a set string string counting up..... all things that will tell you lots if you think about what you are doing.
Debugging. The king of all PC debuggers is IDA
https://www.hex-rays.com/products/ida/ and the older PC versions are free (newer non X86 devices less so). No ifs, no ands, no buts -- IDA is top here and nothing really even comes close for debugging random programs that you have not just written/compiled. Pick a hacking conference and you can be pretty certain that IDA will be the weapon of choice for most there.
However there are others, I do not suggest trying to wrangle the GCC's debugger or some similar dev tool debugger into working for hacking purposes. They are usually great for code but less useful otherwise.
http://www.ollydbg.de/ not even close to IDA but useful enough and certainly worth having in the same way that you might have HxD for when sitting on a machine that is not yours.
http://radare.org/r/ aka radare2. For my money has more functionality than ollydbg, to the point in some cases it might just be able to see IDA in the distance, but the UI (or general lack of it) gets in the way for a lot of people. It also does many things other than X86/X64 out of the box unlike free IDA.
I guess can also link
http://lldb.llvm.org/ though I would use it to flank the others at best in this case.
Likewise if you know the program is written in a scripting language (think Java though that can be messy) or a semi scripting language/lots of libraries language (C# and .net and that family for example) then you might be able to decompile it.
PC debugging in general is a world unto itself so I am not sure I want to even start to truly cover it here, and the oddities inherent to old Japanese games makes it even worse to me to contemplate -- they had some odd ideas about development and used odd formats. That said if you are working with Japanese games then look up the Susie graphics plugin format -- PC game *hacking* got reasonably big over there and many people made graphics decoders using the Susie plugin format.