Deep Q Learning Algorithm for Simple Python Game makes player stuck
This is probably the most major factor:

model.compile(loss='categorical_crossentropy', optimizer='adam')


you have set the loss function for a multiclass classifier. It is going to have some weird results when values - either predicted or target - are outside of range 0..1

You should use this instead:

model.compile(loss='mean_squared_error', optimizer='adam')


because your Q network outputs the expected future return on each action. This could easily be outside of the range that 'categorical_crossentropy' is designed for.

In addition, you really need to look into experience replay. It is not an optional extra when using neural networks with Q learning - it is pretty much required for anything but the most trivial environments. It is very likely your agent will still fail to learn without experience replay, if you correct all other problems with your code.


  I am not sure if the NN architecture (units and hidden layers) is appropriate for given complexity. 


It looks more complex than it needs to be, assuming that your 4 inputs represent paddle x position, particle x,y position and colour. I would suggest making the network simpler (maybe just 40 neurons per layer at a guess), to speed things up a little.

Check your input scaling. Neural networks like to train on inputs that have mean 0, standard deviation 1, and it is worth scaling them so that they fit roughly into -1..1 or similar. Your feature engineering is not shown in your code, so it might be an issue.


  Also, is it possible that this is failing due to the rewards being very delayed? 


This can be a factor that makes learning harder.


  It can take 100+ frames to get to the food, so maybe this isn't registering well with the neural network.


100 time steps delay between rewards is not much for DQN. It should be correctly predicting Q values - it will just take more episodes to learn to predict the best movement when the food is further away.