The representation (as a parallel pair of vectors) isn't as good as the alternative (a single vector of pairs), because:

1. any time the vectors have to grow, there's two separate allocations rather than just one, and
2. whenever they are used, the data may be in different regions of memory (the code has poorer spatial locality).

Consider instead writing

using value_type = std::pair<T, U>;
std::vector<value_type> entries;

This will change the interface a little - in particular, begin() and end() will now give iterators that access these pairs. That's more consistent with std::map interface, so I recommend that.

We can reduce duplication a little: in the initializer-list constructor, we can simply call add() for each element rather than re-writing its body:

template <typename T, typename U>
Dictionary<T,U>::Dictionary (std::initializer_list<std::pair<T,U>> store)
{
    for (std::pair<T,U> object : store) {
        add(object.first, object.second);
    }
}

On the other hand, if we've changed our representation as above, we simply have

template <typename T, typename U>
Dictionary<T,U>::Dictionary (std::initializer_list<std::pair<T,U>> store)
{
    for (std::pair<T,U> object : store) {
        entries.push_back(object);
    }
}

The indexing operator is surprising. If key doesn't exist in the dictionary, then we have undefined behaviour (accessing values out of range). That's a valid choice, but worthy of a comment (particularly as it diverges from the Standard Library interface). Since it doesn't create as necessary, and only ever returns a copy of the value (rather than a reference) it probably ought to be declared const.

We should probably check whether key already exists in add(). We can then either ignore it, or update the existing value. What we have at the moment is the worst possible choice - we add data that can never be used, which only serves to slow future operations.

Some other useful accessors are missing - constant and/or reverse iterators spring to mind as an obvious example, as do methods of removing values. A swap() member would also be very useful.

The has function can be simplified a bit with the use of a standard algorithm: std::any_of() can replace the loop.

Algorithmic complexity

Our operator[] uses linear search with std::find(). Whilst this works, it will get slower in proportion to the number of elements contained - in "big O" notation, we say that it scales as O(n). Once we have the interface as we we want, we'll then want to look at changing the data structure to improve look-up times (and we might need to trade against insertion speed). The good news is that storing items as pairs will work well with whatever storage we choose, and it will be much easier to change the implementation than with separate storage of keys and values.

It may well be worth moving to pair-based storage, and implementing the other review items, and then returning for a performance review of the new code.