Context. The KiDS Strongly lensed QUAsar Detection project (KiDS-SQuaD) is aimed at finding as many previously undiscovered gravitational lensed quasars as possible in the Kilo Degree Survey. This is the second paper of this series where we present a new, automatic object-classification method based on the machine learning technique. Aims. The main goal of this paper is to build a catalogue of bright extragalactic objects (galaxies and quasars) from the KiDS Data Release 4, with minimum stellar contamination and preserving the completeness as much as possible. We show here that this catalogue represents the perfect starting point to search for reliable gravitationally lensed quasar candidates. Methods. After testing some of the most used machine learning algorithms, decision-tree-based classifiers, we decided to use CatBoost, which was specifically trained with the aim of creating a sample of extragalactic sources that is as clean of stars as possible. We discuss the input data, define the training sample for the classifier, give quantitative estimates of its performances, and finally describe the validation results with Gaia DR2, AllWISE, and GAMA catalogues. Results. We built and made available to the scientific community the KiDS Bright EXtraGalactic Objects catalogue (KiDS-BEXGO), specifically created to find gravitational lenses but applicable to a wide number of scientific purposes. The KiDS-BEXGO catalogue is made of ≈6 million sources classified as quasars (≈200 000) and galaxies (≈5.7 M) up to r < 22^m. To demonstrate the potential of the catalogue in the search for strongly lensed quasars, we selected ≈950 “Multiplets”: close pairs of quasars or galaxies surrounded by at least one quasar. We present cutouts and coordinates of the 12 most reliable gravitationally lensed quasar candidates. We showed that employing a machine learning method decreases the stellar contaminants within the gravitationally lensed candidates, comparing the current results to the previous ones, presented in the first paper from this series. Conclusions. Our work presents the first comprehensive identification of bright extragalactic objects in KiDS DR4 data, which is, for us, the first necessary step towards finding strong gravitational lenses in wide-sky photometric surveys, but has also many other more general astrophysical applications.