Project Euler # 62 Cubic permutations in Python
Several issues with your code:


You are storing too much data.
Inefficient usage of Counter()
Is Counter() ordered?
You are needing to guess at upper bounds to the solution
Your timing code is flawed.


Storing too much data

You store the cubes of 1 to \$10^4\$:

cubes = [str(number ** 3) for number in range(1, upper_bound)]


This is then used once as input to computing sorted_cubes, and then once to look up the value at a single index.

When you get an index value from sorted.cubes.index(sorted_cube), say 1000, you look up the value of cubes[1000].  The value at that location will be the string representation of the cube of the 1000th value, which by looking at the range() limits, we can conclude is the \$1001^3\$.

So, you could instead:

return (sorted_cubes.index(sorted_cube) + 1) ** 3


Now that we've removed that pesky final lookup, cubes is only used once in the computation of sorted_cubes, so you can eliminate it entirely.

sorted_cubes = [''.join(sorted(str(number ** 3))) for number in range(1, upper_bound)]


Memory usage has been cut in half.

Inefficient usage of Counter()

As mentioned by @Tweakimp in their answer , you're using Counter() poorly:

count = Counter()
for sorted_cube in sorted_cubes:
    count[sorted_cube] += 1


can be written as:

count = Counter(sorted_cubes)


Is Counter() ordered?

Counter is a dict subclass, and as such on Python 3.6+, it maintains insertion order of the keys.  But in earlier versions, the contents is unordered.

This means, if two or more sets of cubic permutations of the required size are found, in Python 3.6+, the first cube added to the dictionary will be returned first in count.items(), and the correct sorted_cube will be used.  This cannot be relied upon in prior versions of Python.

Guessing at the upper bounds

Where do you need to stop searching for 5 permutations?  How about for 13 permutations?  How about 20?  Where did UPPER_BOUND = 10 ** 4 come from?  Did you just keep increasing it until it worked?

You know there is an answer, so why not keep searching until one is found?  Start at 1 digit cubes, and look for the required number of permutations.  Then try 2 digit cubes, then 3 digit cubes, until an answer is found.  The search space for each would be: \$\sqrt[3]{10^{n}} \le x \lt \sqrt[3]{10^{n+1}}\$, where n is the number of digits in the cube.

Your timing code is flawed.

This code:

START_TIME = perf_counter()
MINIMUM_CUBE = ...
print(f"... {MINIMUM_CUBE} ...")
print(f'Time: {perf_counter() - START_TIME} seconds.')


produces different results on my computer depending on whether the cursor is at the top of a blank terminal window, or at the bottom long scroll of previous text.  Avoid, as much as possible, including printing in timing results.

START_TIME = perf_counter()
MINIMUM_CUBE = ...
END_TIME = perf_counter()
print(f"... {MINIMUM_CUBE} ...")
print(f'Time: {END_TIME - START_TIME} seconds.')


Better implementation

Python 3.6+ only:

def cubic_permutations(required_permutations):
     min_cube = 1
     third = 1/3

     while True:
         max_cube = min_cube * 10 - 1
         lo = int(min_cube ** third)
         hi = int(max_cube ** third)

         cubes = [ "".join(sorted(str(x**3))) for x in range(lo, hi+1) ]
         count = Counter(cubes)
         digits = next((digits for digits, n in count.items()
                        if n == required_permutations), None)

         if digits:
             root = cubes.index(digits) + lo
             return root ** 3

         min_cube *= 10


This code runs over 5 times faster than @Tweakimp's code for their 13 permutation code.  No artificial upper bound is required.  Memory usage is further reduced, since smaller subsets (from lo to hi) of cubes and count are in memory at once.