If you try to call delete on a NULL pointer, it will be ignored.

There's no necessity of a null check like:

if (pointer)
    delete pointer;

Even less:

delete pointer; //Free allocated memory.
pointer = NULL;
delete pointer; //Just to make sure.

That second delete in your code is doing nothing, but it detracts from your code's readability, potentially making it confuse to anyone reading it (even you).

Even if it does no harm directly, it is doing no good either, and I would advise against this.

Always prefer to make clear code and it will make your life way easier when a nasty bug appear!

Don't do that.

Double-delete is a very serious bug.

Sorry about that, fixed the code with what I originally meant to write.

I'm just too used to my overloaded delete that nullifies it for me; my bad.

@ Back on topic,

Under normal circumstances, you delete any objects when you know for sure they won't be reused.
Sometimes that happens during the gameplay, and sometimes at the end.

Still, you can avoid going around calling delete, by, for example, calling a function to make unused objects delete themselves.

#include <algorithms>
#include <vector>

bool exit;

class AwesomeGameObj {
    private:
        static std::vector<AwesomeGameObj*> MasterVector;
        bool isUseless;
    public:
        AwesomeGameObj () {
            /*Initialize everything*/
            isUseless = false;
            MasterVector.pushback(this);
        }
        
        ~AwesomeGameObj () {
            /*Do the cleanup*/
            MasterVector.erase(/*this object*/);
        }
        
        void de_init () {
            while ( !MasterVector.empty() ) {
                delete MasterVector.back();
                MasterVector.pop_back();
            }
        }
        
        bool useless () const {return isUseless;}
        
        static void clean_up () {
            for (/*every object in MasterVector*/)
                if (object->useless()) {
                    vec.erase(/*object*/);
                    delete /*object*/;
                }
        }
        
        static void clean_up (std::vector<AwesomeGameObj*> vec*) {
            for (/*every object in vec*/)
                if ( object->useless() ) {
                    vec->erase(/*object*/);
                    delete /*object*/;
                }
        }
        
        void update () {
            /*do anything it needs to do*/
            if (/*something very very sad happened*/)
                isUseless = true;
        }

};

void quit () {
    AwesomeGameObj::de_init();
    /*do it for any other object types that needs this clean up here*/
}

void init_all () {
    /*init anything*/
}

int main()
{
    //Game Objects in general
    std::vector<AwesomeGameObj*> gameObjects; 
    
    //Fix don't-delete-while-running game objects.
    std::vector<AwesomeGameObj*> miscUseObjects;
    
    init_all();
    
    //Initialize some special objects
    while (/*needs misc objects*/)
        miscUseObjects.push_back (new AwesomeGameObj);
    
    //Main loop
    do {
        while (/*needs new objects*/) {
            gameObjects.push_back (new AwesomeGameObj);
        }
        
        for (/*all gameObjects and miscUseObjects*/) {
            object.update();
        }
        
        if (/*you want to free memory*/)
            AwesomeGameObj::clean_up(gameObjects);
        
    } while (!exit);
    
    //We'll most probably have objects remaining;
    quit();
    
    return 0;
}

As you can see in this example pseudo code, I avoid to call delete on the main and quit functions. I do this by passing on the responsibility of doing so to the object's own class, and all I have to do is tell it to clean up its memory, despite how many objects I need to free and where they are, where they were allocated or anything. This way my main and end functions doesn't have to worry about remaining objects nor freed objects.

std::unique_ptr<Sprite> Background;

Game::Initialize()
{
    // may require a _very_ recent compiler, as make_unique is technically part of the
    // yet-to-be-released C++14, but Visual Studio 2013 has it
    Background = std::make_unique<Sprite>();
    // alternative if you don't have make_unique:
    // Background.reset(new Sprite());
    Background->LoadSprite("bg.bmp");
    /........../
}

Game::Loop()
{
    while(Running){
      while(PollEvent){
         if(KEY == "x"){
           // automatically deletes Background
           Background = nullptr;
        }
     }
   }
}

Game::Quit()
{
    // automatically deletes Background
    // totally safe to call again and again
    Background = nullptr;
}

I may have missed something, but is there a reason to keep the Background object as a pointer? Would it be better to keep it on the stack and rely on it being automatically cleaned up when the Game object dies?

You obviously use a load function to get the texture into memory, you could also use an unload function to remove it from memory if the need exists. And deciding if it should be drawn or not is also something that should exist if you have such requirements, it's easier to give it a bool isDrawn, and instead of deleting the object, simply set it as isDrawn = false. Seems like a nicer choice to me.