Knee pain can go beyond just cleat placement. The asymmetry of the pain does not necessarily imply an incorrectly positioned foot. Other parameters that create pain in one or both knees are the saddle to handlebar distance, saddle height, and crank length. (Saddle angle has some effect, but only in fairly extreme positions. If you have the nose up, your hips ride more to the rear of the saddle, effectively extending your leg length, and vice versa.)
I would recommend adjusting the saddle position first. It is easy to do and requires no additional equipment. If your saddle is too low you can get significant knee pain; knee pain from a saddle too high is less likely as you'll probably notice the rocking motion of your hips on the saddle and reduce the height before you hurt your knees. Similarly, if your saddle position is too far back you can create knee pain (too far forward rarely occurs with the greater set-back of most seatposts).
As for height, a typical starting point is 0.883 x inseam (this is the BB to the top of the saddle, going parallel to the seat tube. As for the saddle to handlebar, there again are many formulas. I typically end up adjusting the saddle so that the front of the saddle is about 1 to 2 cm behind a plomb dropped to the BB. The actual distance to the handlebars is a function of the stem length, the top tube length and the saddle position, all of which will be affected by your riding style and flexibility.
The classic cleat position is to have it so that the pedal axis put opposite the ball of the foot. But there are some who advocate moving this slightly forward of the ball. More important than this slight tweaking is having sufficient float. The SPDs have 6 degrees which is pretty good for most people. (I've had knee surgery and anything less than 3 degrees gives me pain.)
Crank length would be the last to address as it would require additional equipment (ie, another crank of a different length) to test. Formulas for me indicate anywhere from 172.5 mm to 185 mm, which covers a ridiculously large range. In practice, 175 to 180 feels best. A starting value to consider is about 20% of your inseam length.
The inseam length is therefore an important value to try to measure accurately to help you get started. It's easier to measure if someone helps you. Stand with your back against a wall in your stocking feet. Place a hardback book between your legs, with the spine parallel to the floor and against your crotch. Lift it as high as you can comfortably place it. Make sure that the edge that is against the wall is flush to the wall, in order to ensure that the spine is level to the floor. Measure from the ground to the spine.
Good luck, Robert