It sounds like you're doing the right things, but let's check ...
I first used a tool to draw a border around the object I want to cover
Which tool did you use?
Do you have a single layer in your image or have you added more? When you first start out, it is probably best to just keep the one layer. Later you will learn that cloning onto a new layer is much, much better.
I trust that you are working on a copy of your image.