How to build a network that detects common object in images?
You probably just need a deeper network to learn the cross test example. Convolutional layers need to have multiple feature channels and be stacked in order to learn anything more complex that edge/corner counting. Look at example networks for e.g. MNIST and you will usually see typically 2 or 3 CNN layers, with multiple channels (e.g. 32 or 64 channels, each of which is associated with previous layer channels amount of NxN kernels) plus 1 or 2 fully connected layers before classifier.

For a binary choice, yes train on object present/not present classes. There is no major difference between a single sigmoid output or softmax with two outputs. Use cross-entropy loss function, multiclass version if you use softmax. 

I suggest just adapt an MNIST example network to your problem by changing input shape and number of outputs. So that would use softmax and multiclass cross-entropy loss.


  Is it a problem to have a large MaxPooling layer


It could work in some situations, but by having a single layer, single channel CNN, you have made the network too simple to classify even moderately complex shapes. Reducing the activations from this layer to just the max is going to limit the network to essentially classifying by strongest matching 5x5 template to the filter in the image. With enough training examples it should be able to create such a filter, but it would not cope very well with noise, rotation or any partial matches.

You might get something more effective with a large pooling layer over say a 2-deep multi-channel CNN, and then a small fully-connected layer over those max channel outputs. It would still be an unusual choice of architecture, but I suspect it could learn problems like your cross test.