If we're talking a letter of recommendation, I would do my utmost to have a translated copy available from the boss. I don't know how it is in other places, of course, but personally I'd find it a bit weird that this was allegedly the barrier--it would make me wonder if the applicant knew that boss wouldn't give them a good rec, so they were giving me an excuse why I shouldn't call them. So I would provide a translated copy of the LOR (along with the original) and also note on my reference list that Dr. Nakamura speaks Japanese, but no English--in case someone calls her personally. I think this would be very impressive--not only would the applicant strike me as thorough, I would see that they fluently spoke at least one other language and had successfully worked internationally/in a different culture from their own.
On the separate topic of co-workers writing LOR--my boss insists that she's in charge and there's no other hierarchy, so technically I've written LOR for co-workers (vs. lower reports) before. However I've always been able to say that I "helped supervise" the person. I've never written a LOR for someone where I would have to say "I worked alongside" them. Maybe this is a perfectly normal thing in some places/industries, but IME it would be weird. I would be thinking, "This could just be their work buddy who had little professional interaction with them. I want to hear from someone who was in a position to assess their strengths and weaknesses relative to the overall group."
Regarding the first company with high turnover, I think you could put the HR department in your reference list, and perhaps note that none of your previous supervisors are still with the company. Is it possible to find out where at least one of those supervisors is now, and ascertain that they would be a reference for you? If so you could then put them down, even if you had to note that they're now at company X, but supervised you at company Y.