Here are some answers to your questions:
1) If you want your sprite sheet to be compressed (which will reduce memory usage, at the cost of some quality), you will want it to be a power of two. If you are going to do completely uncompressed textures, then any size is OK. My recommendation is to stick with the power of 2, since that gives you the flexibility of using compressed textures if you want later on.
2) Free space in your sprite sheet should not affect your graphics performance, other than using up more memory than necessary. You will want to make your sprite sheets as square as possible. In your example, you have a 640x410 texture. This texture, if set to be compressed, will be scaled up to 1024x1024. You are better off modifying that texture to try and get that 640 pixel width down to 512, so that it becomes a 512x512 texture instead of a 1024x1024.
For creating assets, I would probably create them in 24 bit. If you save them in 32 bit, there will ALWAYS be an 8 bit alpha channel, and that becomes relatively expensive. Since it's a 2D game, there's probably going to be a lot of fully transparent and fully opaque pixels, with very few (if any) partially transparent pixels. My recommendation would be to create a full 24 bit image and then have a separate black and white image for your alpha. For your final format, I would then recommend 16 bit, with 5 bit color and a 1 bit alpha channel.
Overall, you will probably not see significant performance differences between different texture types unless you are graphics bound. The reason this question is difficult to answer without knowing more is that with Unity, there are many things going on simultaneously that can affect performance. Generally, your game is running each frame of the game while the last frame is being rendered. Your frame rate is going to be whichever of those takes the longest. Generally speaking, on mobile, the most expensive things you can do on the rendering side is to have alpha or expensive shaders. Anything that requires multiple passes is going to be particularly expensive. On your game side, heavy memory access and memory allocation are going to be the big performance killers. Destroying and recreating GameObjects rather than having a pool that gets re-used are the types of things that will slow your game code down (but not your rendering).
From your original description, I would agree with what other replies to your questions have said. If your graphics performance is getting worse over time, you are probably not being slowed down by the graphics (unless the graphics get consistently more complex over time). If there's a specific section that, when on camera, slows things down, then it might be rendering, but if its just getting slower over a period of time, then my first guess would be that you are creating something that is not getting destroyed, so the scene is getting busier as time progresses, which is reducing your frame rate.
More info on textures and texture sizes
Unity has a few different texture types that you can set, and depending on what the setting is, as well as what is contained in the texture you are applying it to will affect what it turns into by the different settings.
TrueColor - This means that Unity is not doing anything to the color/pixel values in your texture, so they are "true". True color textures can be any width or height.
If your texture has any alpha in it, this means it will create a 32 bit texture. A 32 bit texture's size is going to be width*height*4. It has a full 8 bit alpha for each pixel.
If your texture doesn't have any alpha in it, it will create a 24 bit texture. A 24 bit texture's size is going to be width*height*3. It will have no alpha, and adding even a single pixel of alpha will make it convert to 32 bit, so it will become 33% bigger.
16 bit - A 16 bit texture is going to be either 2/3 the size or 1/2 the size of a true color texture, depending on whether the 32 bit texture has alpha or not. Its total size will be width*height*2. 16 bit textures can also be any size, like true color. They are smaller than true color, but at the loss of some color resolution. You will get mixed results on this setting, but they do have the advantage of supporting alpha without changing the size, and are not compressed.
Compressed - A compressed texture is significantly smaller than either a True Color or 16 bit texture. The compression will look better on some textures than others, and its beyond the scope of this explanation to give you hints on how to improve the visual quality. A compressed texture must be a power of two, and if it is not, Unity will automatically scale it up to the next largest power of two. A compressed texture is generally significantly faster to render and uses a much smaller amount of memory, and can carry an alpha channel. It tends to look best on things that are "noisy", so real pictures, or things that are busy. It tends to look worse on things that are flat colors or have sharp edges that are important. So fonts, text, and UI elements will probably have more obvious signs of compression than a texture of a tree, for example.
