In general yes, reinforcement learning can reason about agents who lack full knowledge of their environment, namely through partially observable Markov decision processes (POMDPs). These generalize MDPs by adding a set $\Omega$ of observations and set $O$ of probabilities of observations, conditioned on state and action.
Where in a normal MDP state is deterministically known, POMDPs reason about probabilistic belief across the state space. (You could think of an agent's belief in an standard MDP as $1$ for the state the agent is in, $0$ else.)
(To learn more about this class of problems, you might consult lesson 10 of the udacity & Georgia Tech RL course.)
That said, in the terminology of MDPs, your problem is fully observed. Think of the single shelf in your example as a binary string of length $10$, with values of $1$ if the space is filled, $0$ else. You can now represent your state space as a tuple of this string, the length of the box in the queue (or null if none), and the address of a box to remove (or null if none).
At any given time step, you know where all the boxes are on the shelves, and you know the size of the box you need to place. When you place that box, you know deterministically where it goes, and which binary values to flip to $1$. Given a remove action, you know which values to flip to $0$.
What you don't know is whether you'll get a remove or place command, and what size the next place. An MDP accounts for this uncertainty in the transition function $T(s,a,s')$, which gives the probability of winding up in a state $s'$ after taking action $a$ in state $s$.
Some methods model the transition function explicitly; others learn without representing $T$. Which is best is another question, and in either case you'd need a reward function that could formalize "maximize storage."