Is it normal to have some soreness in your knees after cycling with SPD? I recently got some SPD pedals. Initially, my seat was too high (old pedals added about 3/4th of an inch to height), and at the end of the downstroke, pulled uncomfortably on my knees. After even moderate rides (~5k), it would be painful walking up stairs, for example.

Anyway, figured that part out, lowered my seat, no problems for several weeks. Weather gets better, start ramping up the distance I travel, and now I find that I get a (much) less painful version of the same thing after longer rides (>40k) with a headwind. 

Is it normal to get some soreness in your knees, or is this a sign that the seat is still not at the right height? Is there an algorithmic way to adjust seat height?
If your bike is set up with a proper fit to your body, and your pedal's cleat position is set up for your body, soreness in your knees like you describe is not normal. 

Whether the discomfort you are experiencing is simply muscle soreness, as in "I exercised heavily and my body noticed" or whether it requires corrective action, is harder to decide. 

If the discomfort is only after heavy exercise, like 40+ km rides in a headwind, I'd be inclined to say its because the pedals are new to you, and you're building the muscle you need to use them, as your body adapts to pulling up, not just pushing down on the pedal.

However, if this continues to be an issue for more than a few weeks, consider having a bike fit done which includes cleat positioning.

Also, if you are not riding off road, and you have purchased mountain bike style SPDs, rather than the road version, consider getting the larger and more supportive version. Unfortunately, this would usually also require new shoes, but many riders report cramps, hot spots, and muscle soreness when riding longer, uninterrupted distances on MTB clipless pedal designs.