Steve,
You are going to have to struggle to wrap your brain around the issue of pixel size, resolution, and print size. At first it always seems obscure at best, but it is a vital bit of Photoshop knowledge. In the top Image Size dialog, I've set up an image dimension of your camera's output and then changed the resolution to 300 with the resample unchecked. This means that the maximum print size you can have without resampling the image (think of that? as increasing or decreasing the number of pixels), is too small to fill an A4 paper size. You must resample the image (increase the number of pixels).
So I've resampled the image to fit the A4 Length in the bottom Image Size dialog. Note that the proportions of your original capture (photograph) aren't the perfect proportion for a completely filled A4 paper size. This is where you have to start adjusting your mental ideas to the reality. You wouldn't wish to change the proportions, I believe, so you're stuck with a border.
If you wished to automate your image resizing for print and all your images were the same size and orientation (landscape/portrait), you could record an action to open the image, rotate it from landscape orientation to portrait, resize it and save. In order to learn how to do that, look in Photoshop Help > Actions also there are a zillion Googlable sources for learning about creating actions in PS.
Good luck!