The need of Scrum isn't to complete every story at the end of every sprint. In fact, that might not happen, especially early in a project when you are still settling on a velocity. The idea is to have a potentially shippable (working, tested, and documented) product that adds business value to the customer at the end of every iteration.
The first thing to do is to improve your definition of done. Done should mean that the story is complete. That means it has been designed, implemented, unit tested, integrated and passed system and acceptance tests. When a story is done, that means the feature or capability that the store represents is ready for delivery to the customer. The Scrum Alliance has some articles on what a good definition of done looks like, how to know when you are done with a story, and a methodology for creating a good definition of done.
Next, you should probably begin to work on your estimation and planning. It shouldn't be a continual struggle to incorporate the stories into each release. It begins with having appropriate and accurate estimates as to the size of the story, which often uses story points to provide an estimation of the relative effort required to complete the story. Once you have estimates, you need to use these estimates to plan. If you find yourself finishing 10 story points every sprint, don't pull more than 10 story points into the next sprint. If you pulled 10 story points into one sprint, but only finished 8 of them, only include 8 in the next sprint. If you finish early, you can either pull in more story points or use the additional time to reduce technical debt by refactoring, writing new automated tests, or improving existing tests (as a few examples).
Rather than starting the next sprint immediately, make sure you have time for your retrospective and planning meetings. Use this as an opportunity to determine what was problematic or needs improvement, and then implement corrections for the process in future sprints.
I think that doing this will resolve some of your problems, and make others easier to fix, or at least bring out more information. Some of the problems are also related to organizational culture, such as the entire team participating in testing or not using pair programming. Eventually, you are going to want to get the entire team into testing (and other activities), since Scrum is centered around a team that has cross-functional skills. Improved estimation will also help you identify if your stories are too large. As far as pair programming - it's a non-issue, since it's not required for Scrum and might not be of use to your team.
