You are correct about the second point. The computational complexity would be # Lights x # Objects. But with a simpler shader this wouldn't be too much of a problem. As it is at the moment the complexity of your shader is proportional to the # Lights (because of the for loop) and you execute it once per object. So you are already on par with that anyway, but you will remove branching in the shader by not requiring the for loop, you could also use a different pixel shader for each different type of light removing the need for another if statement. Further more you can check if the object to be rendered is within range of the light and just exclude it from being drawn completely.
You say the problem only occurs when you are close to the object, this is most likely because there are more pixels filling the screen, thus more executions for the pixel shader, thus more time spent on computations. I would suggest you disable vsync (if you havn't already) then you will probably notice the performance differences and how they change.