To supplement the other reviews, here are some other things you might improve.

Use override where appropriate

When a virtual function is being overridden, it should be marked either override or final to allow catching errors at compile time. See C.128.

Make sure all paths return a value

The setType routine claims it returns an int but it does not. That's an error that should be addressed.

Don't use std::endl if you don't really need it

The difference betweeen std::endl and '\n' is that '\n' just emits a newline character, while std::endl actually flushes the stream. This can be time-consuming in a program with a lot of I/O and is rarely actually needed. It's best to only use std::endl when you have some good reason to flush the stream and it's not very often needed for simple programs such as this one. Avoiding the habit of using std::endl when '\n' will do will pay dividends in the future as you write more complex programs with more I/O and where performance needs to be maximized.

Think carefully about object ownership

The traditional role of a shelter is to take in animals and then give them to a new owner on adoption. This shelter seems to only do bookkeeping of the location of animals (by handling only pointers) rather than actually taking ownership of them. What is actually a more appropriate way to express this is by the use of a std::unique_ptr. See R.20

Think carefully about the domain and range of numbers

The _queueOrder increases without bound and is used to assign the _order of each animal. What happens when that number wraps around?

Use polymorphism effectively

Whenever you find yourself writing code like this:

if (animal->getClassName() == "Cat") {
        Cat* d = dynamic_cast<Cat*>(animal);

stop and question whether this is really needed. By using animal->getClassName() as a sort of home-grown polymorphism, the code is made much more brittle and hard to maintain. Here's how I'd write that using a std::unique_ptr instead:

void enqueue(std::unique_ptr<Animal> &&animal) {
    animal->setOrder(++queueOrder);
    if (typeid(*animal) == typeid(Cat)) {
        catQueue.push_back(std::move(animal));
    } else if (typeid(*animal) == typeid(Dog)) {
        dogQueue.push_back(std::move(animal));
    } else {
        throw std::runtime_error("This animal is not suitable for the shelter");
    }
}

Note that this uses true RTTI, built into the language, instead of inventing a poor imitation. It also throws an error if the passed animal is neither a cat nor a dog. This could be handy if someone attempted to drop off a pet rhinocerous.

Don't expose class internals

It seems to me that getDogQueue and getCatQueue are both ill-advised and unneeded. I'd simply omit them both.

Base destructors should be virtual

The destructor of a base class, including a pure virtual one like Animal, should be virtual. Otherwise, deleting the object could lead to undefined behavior and probably memory leaks.

Consolidate common items into a base class

Since all of the derived classes have _name, why not move that functionality into the base class?

Use const where practical

The getName() function does not alter the underlying class because it returns a copy of the name. Similarly, the getClassName() function does not alter the class. Both should be declared const.

Use standard operators

Rather than the vaguely named Compare, better would be to simply use the standard operator<. Here's how I'd write it as a member function of Animal:

bool operator<(const Animal& b) const {
    return _order < b._order;
}

Use better names

Most of the names are not bad, but rather than AnimalQueue and enqueue and dequeue, I'd suggest giving them more usage-oriented names rather than describing the internal structure. So perhaps AnimalShelter, dropoff and adopt would be more suitable.

Think carefully about data types

If you use a std::deque instead of a std::queue, you gain access to iterators which are useful for printing as shown in the next suggestion.

Use an ostream &operator<< instead of display

The current code has printQueue() function but what would make more sense and be more general purpose would be to overload an ostream operator<< instead. This renders the resulting function much smaller and easier to understand:

friend std::ostream& operator<<(std::ostream& out, const AnimalShelter& as) {
    out << "\nCat Queue\n";
    for (const auto& critter : as.catQueue) {
        out << *critter << '\n';
    }
    out << "\nDog Queue\n";
    for (const auto& critter : as.dogQueue) {
        out << *critter << '\n';
    }
    return out;
}

I also modified the base class to include _name as mentioned above and wrote this friend function of Animal:

friend std::ostream& operator<<(std::ostream& out, const Animal& a) {
    return out << a.getClassName() << ' ' << a._name << ' ' << a._order;
}

Implement the problem specification completely

The description of the problem mentions that one might be able to adopt either a cat or a dog or the first available, but only the latter function has been implemented. Here's how I wrote all three:

std::unique_ptr<Animal> adopt() {
    std::unique_ptr<Animal> adoptee{nullptr};
    if (catQueue.empty() && dogQueue.empty())
        return adoptee;

    if (catQueue.empty()) {
        std::swap(adoptee, dogQueue.front());
        dogQueue.pop_front();
    } else if (dogQueue.empty() || (catQueue.front() < dogQueue.front())) {
        std::swap(adoptee, catQueue.front());
        catQueue.pop_front();
    } else {
        std::swap(adoptee, dogQueue.front());
        dogQueue.pop_front();
    }
    return adoptee;
}

std::unique_ptr<Animal> adoptCat() {
    std::unique_ptr<Animal> adoptee{nullptr};
    if (!catQueue.empty()) {
        std::swap(adoptee, catQueue.front());
        catQueue.pop_front();
    }
    return adoptee;
}

std::unique_ptr<Animal> adoptDog() {
    std::unique_ptr<Animal> adoptee{nullptr};
    if (!dogQueue.empty()) {
        std::swap(adoptee, dogQueue.front());
        dogQueue.pop_front();
    }
    return adoptee;
}

Results

Here is the modified main to exercise the revised code:

int main()
{   
    AnimalShelter shelter;
    shelter.dropoff(std::move(std::unique_ptr<Animal>(new Dog{"Max"})));
    shelter.dropoff(std::move(std::unique_ptr<Animal>(new Cat{"Trace"})));
    shelter.dropoff(std::move(std::unique_ptr<Animal>(new Cat{"Han"})));
    shelter.dropoff(std::move(std::unique_ptr<Animal>(new Dog{"Shaun"})));
    shelter.dropoff(std::move(std::unique_ptr<Animal>(new Dog{"Tiger"})));
    shelter.dropoff(std::move(std::unique_ptr<Animal>(new Cat{"Meow"})));
    try {
        shelter.dropoff(std::move(std::unique_ptr<Animal>(new Rhino{"Buster"})));
    } catch (std::runtime_error &err) {
        std::cout << err.what() << '\n';
    }
    std::cout << shelter << '\n';

    for (int i = 0; i < 2; ++i) {   
        auto pet = shelter.adoptDog();
        if (pet) {
            std::cout << "You have adopted " << *pet << "\n";
        } else {
            std::cout << "sorry, there are no more pets\n";
        }
        std::cout << shelter << '\n';
    }

    for (int i = 0; i < 6; ++i) {  // adopt any
        auto pet = shelter.adopt();
        if (pet) {
            std::cout << "You have adopted " << *pet << "\n";
        } else {
            std::cout << "sorry, there are no more pets\n";
        }
        std::cout << shelter << '\n';
    }

    std::cout << "Final: \n" << shelter << '\n';
}