There are mamy many possibilities.
I'll get just the smallest and the largest possibile solutions.

The smallest prime is 2

It's cube is 2³ or 8

The smallest number we can add to 8 to get a 4-digit number is
1000-8=992.  But 992 is not a square, so we want to add the smallest
square bigger than 992. To do that we get its square root which
is about 31.496. Then the next whole number bigger than that,
which is 32, is such that if we square it and add it to 8, it
will be the cube of a prime number plus a square.

So we add 

2³ + 32³ = 8 + 1024 = 1032

That's the smallest possible solution, 1032.

Let's start with the largest prime whose cube is a 
4 digit number.  That's the prime number 19, because 
19³ = 6859, a four-digit number whereas the next prime 
23³ = 12167, which is a five-digit number. 

It's cube is 19³ or 6859

The largest number we can add to 6859 to get a 4-digit number is
9999-6859=3140.  But 3140 is not a square, so we want to add the largest
square smaller than 3140. To do that we get its square root which
is about 56.036. Then the largest whole number smaller than that,
which is 56, is such that if we square it and add it to 6859, it
will be the cube of a prime number plus a square.

So we add 19³ + 32³ = 8 + 1024 = 1032

19³ + 56² = 9995

That's the largest possible solution.

Edwin