How can I add column titles into a Dataset?

I think what you need is more like this:

dat=Dataset[MapThread[<|"Country" -> #1,"Population" -> #2|> &, {Countries, populations}]]

The structure you are looking for is one association per row, with the keys equal to the column headings.

One option could be

 PrependTo[dat, <|"Country" -> "Population"|>]

I do not know how the semantics of your data set will change now by adding the title right into the data itself like this. I think normally column titles are added at the end, for display purposes and not part of the actual dataset itself.