In the following is object the same as an instance. Actually an object is the instance of a symbol or class.
If I add an object to a layer, and then add a keyframe to the existing frame set, are there now two instances of the object, one for each frame?
You look at key frames separately. In both frames there is one instance each. If both instances have the same instance name, you can say that they are identical, although the actual instance parameters of them can completely differ (like size, position, color, effects etc.).
When I change the color of the instance in the first key frame, the second keyframes instance stays the same. Is there anyway to edit across all frames? Paste across all frames?
When you are editing an instance's color, or in general its instance parameters, you only affect the current instance you are editing. Even if two instance's have the same instance name, they are completely different objects and both have independent instance parameters.
If you want to share things across multiple instances you can either modify the symbol itself (which changes all instances) or you could wrap a symbol's instance in another symbol which you then instanciate multiple times. The first symbol's instance parameters then can be changed and apply to all instances of the second symbol.